Polynomial basis multiplication over \(\text{GF}(2^m)\) (Q850783)

The purpose of this survey is, in the authors' words, ``to describe, analyze and compare various \(\text{GF}(2^m)\) multipliers''. Efficient hardware and software implementations of the multiplication in binary finite fields \(\text{GF}(2^m)\), with \(m\) large, are crucial in applications such as Cryptography. The authors argue that ``multiplication methods that use polynomial base representations are very efficient in comparison to the best methods using other basis representations''. Section 2 of the paper introduces to the problem of polynomial basis multiplication of two \(\text{GF}(2^m)\) elements and its two main stages: multiplication of two degree \(m-1\) polynomials \(a(x), b(x)\) and reduction of the product \(d(x)\) modulo the degree \(m\) irreducible polynomial \(\omega(x)\) defining \(\text{GF}(2^m)\), to obtain a field element \(c(x)\). In Section 3 the authors calculate the space and time complexity of these two arithmetic operations. Particular attention is paid to the cases \(\omega(x)\) an equally spaced polynomial and \(\omega(x)\) an \(r\)-nomial, cases that provide better complexity in the modular reduction. Section 4 of the paper reviews the matrix vector product techniques. An approach is to reduce the polynomial \(d(x)\) using an \((m \times m-1)\) reduction matrix, defined in terms of \(\omega(x)\). A second approach is to simultaneously perform the polynomial multiplication and the reduction operation using the so-called (\(m\times m\)) Mastrovito matrix, whose entries are function of the coefficients of \(\omega(x)\) and the polynomial \(a(x)\) (the multiplicand), see [\textit{E. D. Mastrovito}, Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conference, AAECC-6, Rome/Italy 1988, Lect. Notes Comput. Sci. 297--309 (1988; Zbl 0673.94024)]. Tables with complexities for both techniques are provided. Finally the Montgomery multiplication method is explained in Section 5. The Montgomery multiplication [see \textit{C. K. Koc} and \textit{T. Acar}, Des. Codes Cryptogr. 14, No. 1, 57--69 (1998; Zbl 0887.11054)] calculates \(c(x)=a(x)b(x)r(x)^{-1} \bmod \omega(x)\), where \(r(x)\) is a fixed polynomial (Koc and Acar take \(r=x^m\)). The special case where \(\omega(x)\) is an irreducible trinomial gives good space and time complexity.