- A polynomial basis is specified by an irreducible polynomial modulo 2, called the field polynomial. The bit string (am-1 … a2 a1 a0) is taken to represent the polynomial am-1tm-1 + … + a2t2 + a1t + a0
over GF(2). The field arithmetic is implemented as polynomial arithmetic modulo p(t), where p(t) is the field polynomial.
- A normal basis is specified by an element θ of a particular kind. The bit string (a0 a1 a2 … am-1) is taken to represent the element a0θ + a1θ2 + a2θ22 + am-1θ2m-1
Normal basis field arithmetic is not easy to describe or efficient to implement in general, but is for a special class called Type T low-complexity normal bases. For a given field degree m, the choice of T specifies the basis and the field arithmetic (see Appendix 6.2).
There are many polynomial bases and normal bases from which to choose. The following procedures are commonly used to select a basis representation.
- Polynomial Basis: If an irreducible trinomial tm + tk + 1 exists over GF(2), then the field polynomial p(t) is chosen to be the irreducible trinomial with the lowest-degree middle term tk. If no irreducible trinomial exists, then one selects instead a pentanomial tm + ta + tb + tc + 1. The particular pentanomial chosen has the following properties: the second term ta has the lowest degree m; the third term tb has the lowest degree among all irreducible pentanomials of degree m and second term ta; and the fourth term tc has the lowest degree among all irreducible pentanomials of degree m, second term ta, and third term tb.
26
