Optimal Normal Basis Representation
For many values of m, the finite field F2m has an optimal basis representation as well as the polynomial representation described above. An optimal basis gives an alternative way of defining multiplication on the elements of a field. While optimal normal basis multiplication is less insightful than polynomial multiplication, it is in practice much more efficient.
Setup for Multiplication
Optimal normal basis representations are classified as either Type I or Type II. The value of m determines which type shall be used.
- If F2m only has a type I ONB then let f(x) = xm + xm-1 + ... + x2 + x + 1. Otherwise, if F2m has a type II ONB then compute f(x) = fm(x) using the following recursive formulae:
f0(x) = 1,
f1(x) = x + 1,
fi+1(x) = xfi(x) + fi-1(x), i = 1, ..., m.
At each stage, the coefficients of the polynomials fi(x) are reduced modulo 2; hence f(x) is a polynomial of degree m with coefficients in F2. The set of polynomials {x, x2, x22, ..., x2m-1} forms a basis of F2m over F2, called a normal basis. - Construct the m by m matrix A whose ith row, i = 0 ... m - 1, is the bit string corresponding to the polynomial x2i mod f(x). (The rows and columns of A are indexed by the integers from 0 to m - 1.) The entries of A are elements of F2.
- Determine the inverse matrix A-1 of A over F2.
- Construct the m by m matrix T ' whose ith row, i = 0 ... m - 1, is x x2i mod f(x). Then compute the matrix T = T ' A-1 over F2.
- Determine the product terms lij, for i, j = 0 ... m - 1, as lij = T(j-i,-i). (T(g,h) denotes (g,h)-entry of T with indices reduced modulo m.) Each product term lij is an element of F2. It should also be the case that l0j = 1 for precisely one j, 0 <= j <= m - 1, and that for each i, 0 <= i <= m - 1, lij = 1 for precisely two distinct j, 0 <= j <= m - 1. Hence only 2m-1 of the m2 entries of the matrix T are 1, the rest being 0. This scarcity of 1's is the reason that the normal basis is called an optimal normal basis.
Certicom is a trademark of the Certicom Corp. Copyright Certicom Corp. 1997. All rights reserved.
