STRUCTURAL COMPLEXITY OF MULTIPLIERS FOR GALOUAN FIELDS ELEMENTS IN NORMAL AND POLYNOMIAL BASES

Abstract

Currently, the mathematical basis for digital signature processing are elliptic curves. Elliptic
curve points processing is based on the performance of operations in Galois field GF(2m
) in normal or polynomial bases. Characteristics of multipliers for these bases are different. Software implementation for polynomial basis multiplier is one to two orders faster than one for normal basis implementation. Hardware implementations have similar hardware and time complexity. But normal basis multiplier provides a time constant inverse element calculation, and in the polynomial basis that time depends on the operands. The study
of the structural complexity of multipliers is based on the use of an imaginary FPGA, all its logical elements
can implement an arbitrary function of two variables. The structural complexity is estimated as the total
length of studied unit links in the FPGA topology. It is shown that the structural complexity of parallel multipliers for normal and polynomial bases can be estimated as O(m3
) and O(m2
), respectively. The lower structural complexity for polynomial basis multipliers allow to create their multisection versions with higher
number of sections (with higher concurrency and therefore better performance) than similar multipliers for
normal basis.