Arithmetic of polynomials
A commonly used representation for the elements of a finite field F_{(/}, where q = p^{m} and p is a prime, is a polynomial basis representation. If m = 1, then F_{9} is just Z_{p} and arithmetic is performed modulo p. Since these operations have already been studied in Section 2.4.2, it is henceforth assumed that m > 2. The representation is based on Fact 2.198.
2.224 Fact Let f(x) € Z_{p}[x be an irreducible polynomial of degree m. ThenZ_{P}[x]/(f{x)) is a finite field of order p^{m}. Addition and multiplication of polynomials is performed modulo
f{x).
The following fact assures that all finite fields can be represented in this manner.
2.225 Fact For each m > 1, there exists a monic irreducible polynomial of degree m over Z_{p}. Hence, ever}' finite field has a polynomial basis representation.
An efficient algorithm for finding irreducible polynomials over finite fields is presented in §4.5.1. Tables 4.6 and 4.7 list some irreducible polynomials over the finite field Z2.
Henceforth, the elements of the finite field F_{p}». will be represented by polynomials in Z_{p}[x of degree < m. If g(x), h(x) e F_{p}m, then addition is the usual addition of polynomials in Z_{p}[x. The product g(x)h(x) can be formed by first multiplying g(x) and h(x) as polynomials by the ordinary method, and then taking the remainder after polynomial division by f(x). Multiplicative inverses in F_{p}m can be computed by using the extended Euclidean algorithm for the polynomial ring Z_{p}[a:].
2.226 Algorithm Computing multiplicative inverses in F_{p}™
INPUT: a nonzero polynomial r/(x) e F_{p}m. (The elements of the field F_{p}m are represented as Z_{p}[x]/(f(x)), where f(x) € Z_{p}[x] is an irreducible polynomial of degree m over Z_{p}.) OUTPUT: g{x)~^{l} 6 F_{p}™.
 1. Use the extended Euclidean algorithm for polynomials (Algorithm 2.221) to find two polynomials s(x) and t(x) € Z_{p}[x such that s(x)g(x) + t(x)f(x) = 1.
 2. Retum(.s(.x')).
Exponentiation in F_{p}m can be done efficiently by the repeated squareandmultiply algorithm (cf. Algorithm 2.143).
2.227 Algorithm Repeated squareandmultiply algorithm for exponentiation in F_{p}»<
INPUT: g(x) e F_{p}». and an integer 0 < k < p^{m}  1 whose binary representation is к = Xa=o (The field F_{p}m is represented as Z_{p}[x]/(f(x)), where f(x) e Z_{p}[x] is an irreducible polynomial of degree m over Z_{p}.)
OUTPUT: g{x)^{k} mod f{x).
 1. Set s(x)'*l. If к = 0 then retum(s(x)).
 2. Set G(x)t— g(x).
 3. If k_{0} = 1 then set s(x)^g(x).
 4. For i from 1 to t do the followmg:
 4.1 Set G(x)<—G(x)^{2} mod f(x).
 4.2 If ki = 1 then set s(x)<— G{x) ■ s(x) mod f(x).
 5. Retum(.s(.x')).
The number of Z_{p}operations for the basic operations in F_{p}m is summarized in Table 2.8.
Operation 
Number of Z_{p}operations 

Addition 
g(x) + h(x) 
О (in) 
Subtraction 
g(x)  h(x) 
О (in) 
Multiplication 
g(x) ■ h(x) 
О (in^{2}) 
Inversion 
а&у^{1} 
0(m^{2}) 
Exponentiation 
g(x)^{k}, к < p^{m} 
0((lgp)m^{3}) 
Table 2.8: Complexity of basic operations in F_{p}m.
In some applications (cf. §4.5.3), it may be preferable to use a primitive polynomial to define a finite field.
2.228 Definition An irreducible polynomial f(x) € Z_{p}[x] of degree m is called a primitive polynomial if x is a generator of F_{p}..«, the multiplicative group of all the nonzero elements
in Fpm = Z_{p}[x]/(/(x)).
2.229 Fact The irreducible polynomial f(x) e Z_{p}[x] of degree m is a primitive polynomial if and only if f(x) divides x^{k} — 1 for к = p^{m} — 1 and for no smaller positive mteger k.
 2.230 Fact For each m > 1, there exists a moiiic primitive polynomial of degree m over Z_{p}. In fact, there are precisely ф(р^{т}  1 )/m such polynomials.
 2.231 Example {the finite field F_{2}j of order 16) It can be verified (Algorithm 4.69) that the polynomial f(x) = x^{4} + x + 1 is irreducible over Z_{2}. Hence the finite field F_{2}i can be represented as the set of all polynomials over F_{2} of degree less than 4. That is,
For convenience, the polynomial 03a;^{3} + a_{2}x^{2} + ax + a_{0} is represented by the vector
(озо_{2}а.1ао) of length 4, and
The following are some examples of field arithmetic.
 (i) Field elements are simply added componentwise: for example, (1011) l (1001) =
 (0010).
 (ii) To multiply the field elements (1101) and (1001), multiply them as polynomials and then take the remainder when this product is divided by fix):
Hence (1101) • (1001) = (1111).
 (iii) Tlie multiplicative identity of F_{2}4 is (0001).
 (iv) The diverse of (1011) is (0101). To verify this, observe that
whence (1011) • (0101) = (0001).
f(x) is a primitive polynomial, or, equivalently, the field element x = (0010) is a generator of F_{2}4. This may be checked by verifying that all the nonzero elements in F_{2}4 can be obtained as a powers of x. The computations are summarized in Table 2.9. □
A list of some primitive polynomials over finite fields of characteristic two is given in Table 4.8.