Page 251 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 231

m LUTs Slices Total time Polynomial
8 56 28 4 x + x + x + x + 1
3
8
4
3
64 3,480 2,011 10 x + x + x + x + 1
4
64
5
2
3
200 33,624 19,306 ∞ x 200 + x + x + x + 1
12
5
7
283 67,110 33,555 ∞ x 283 + x + x + x + 1
∞ means that the circuit does not fit within the device.
TABLE 7.20 Cost and Delay for Class 1 Pentanomials
7.8 Comments and Conclusions
According to the implementation results, the following conclusions
are obtained.
1. For modular multipliers, combinational circuits are too
expensive in terms of area for big polynomials in cases that can’t
be implemented in a single device. Sequential implementations
need m (degree of f(x)) cycles to obtain a result and could be too
slow. A trade-off can be obtained using a sequential circuit that
computes G bits per cycle. Tables 7.5 and 7.6 show results for the
163- and 233-bits NIST-recommended polynomials.
2. Regarding squaring, combinational circuits are simpler and
faster than the corresponding sequential circuits.
3. For exponentiation, the computation time depends on the
number of ones in the exponent and the multiplication deter-
mines the worst time. For faster exponentiation, multipli-
cation such as in Sec. 7.7.5 should be used.
4. For division-inversion, the binary division can be used for in-
version with good results. The MAIA inversion has the critical
path in the computation of the degree of polynomials.
5. For multipliers with special irreducible polynomials (AOPs,
trinomials, pentanomials), combinational circuits have the
same area problems as combinational multipliers with general
irreducible polynomials, but with a lower complexity (area,
delay).

7.9 References
[ABMV93] G. B. Agnew, T. Beth, R. C. Mullin, and S. A. Vanstone. “Arithmetic
m
operations in GF(2 ).” Journal of Cryptology, vol. 6, no. 1, pp. 3–13, 1993.
[Ara93] B. Arazi. “Architectures for Exponentiation Over GF(2 ) Adopted for Smartcard
n
Application.” IEEE Transactions on Computers, vol. 42, no. 4, pp. 494–497, April 1993.
[BCH93] H. Brunner, A. Curiger, and M. Hofstetter. “On Computing Multiplicative
m
Inverses in GF(2 ).” IEEE Transactions on Computers, vol. 42, no. 8, pp. 1010–
1015, August 1993.