# Finite fields

## Basic properties

2.208 Definition *Apiite field* is a field *F* which contains a finite number of elements. The *order *of *F* is the number of elements in *F.*

- 2.209 Fact (
*existence and uniqueness of finite fields)* - (i) If
*F*is a finite field, then*F*contains*p*elements for some prime^{m}*p*and integer*m >*1. - (ii) For every prime power order
*p*there is a unique (up to isomorphism) finite field of order^{m},*p*This field is denoted by F^{m}._{p}m, or sometimes by*GF(p*^{m}).

Informally speaking, two fields are *isomorphic* if they are structurally the same, although the representation of their field elements may be different. Note that if *p* is a prime then Z* _{p}* is a field, and hence every field of order

*p*is isomorphic to Z

_{p}. Unless otherwise stated, the finite field F

_{p}will henceforth be identified with Z

_{p}.

- 2.210 Fact If Fq is a finite field of order
*q = p*a prime, then the characteristic of F,^{m}, p_{;}is*p.*Moreover, F_{(/}contains a copy of Z_{p}as a subfield. Hence F_{(/}can be viewed as an extension field of Z_{p}of degree m. - 2.211 Fact
*(subfields of a finite field)*Let F_{4}be a finite field of order*q*=*p*Then every subfield of Fq has order^{m}.*p*for some^{n},*n*that is a positive divisor of m. Conversely, if*n*is a positive divisor of m, then there is exactly one subfield of F_{4}of order*p*^{n}; an element*a*€ F_{4}is in the subfield F_{p}>. if and only if*a*^{p}" =*a.* - 2.212 Definition The non-zero elements of F
_{9}form a group under multiplication called the*multiplicative group*of Fq, denoted by F*. - 2.213 Fact F* is a cyclic group of order
*q**—*1. Hence*a*=^{q}*a*for all*a e*Fq. - 2.214 Definition A generator of the cyclic group F* is called a
*primitive element*or*generator*Of Fq.

2.215 Fact If *a, b* € F_{9}, a finite field of characteristic *p,* then

## The Euclidean algorithm for polynomials

Let Z_{p} be the finite field of order *p.* The theory of greatest common divisors and the Euclidean algorithm for integers carries over in a straightforward manner to the polynomial ring *Z _{p}[x]* (and more generally to the polynomial ring

*F[x],*where

*F*is any field).

- 2.216 Definition Let
*g{x), h(x)*€ Z_{p}[x], where not both are 0. Then the*greatest common divisor*of*g(x)*and*h(x),*denoted gcd(g(x),*h(x)),*is the monic polynomial of greatest degree in Z_{p}[x] which divides both*g(x)*and*h(x).*By definition, gcd(0,0) = 0. - 2.217 Fact Z
_{p}[x] is a*unique factorization domain.*That is, every non-zero polynomial /(x) e Z_{p}[x] has a factorization

where the /;(x) are distinct monic irreducible polynomials in Z_{p}[x], the *e,* are positive integers, and *a* € Z_{p}. Furthermore, the factorization is unique up to rearrangement of factors.

The following is the polynomial version of the Euclidean algorithm (cf. Algorithm 2.104).

2.218 Algorithm Euclidean algorithm for *Z _{p}[x]*

INPUT: two polynomials *g{x), h(x)* € *Z _{p}[x}.*

OUTPUT: the greatest common divisor of *g(x)* and *h(x).*

- 1. While
*h(x*)*ф*0 do the following: - 1.1 Set r(ar)-t—
*g(x)*mod*h(x), g(x)<—h(x), h(x)<—r(x).* - 2. Retum(g(x)).
- 2.219 Definition A
*Z*means either an addition, subtraction, multiplication, inversion, or division in_{p}-operation*Z*_{p}. - 2.220 Fact Suppose that deg
*g(x)*< m and deg*li(x) < m.*Then Algorithm 2.218 has a running time of 0(m^{2}) Z_{p}-operations, or equivalently, 0(ra^{2}(lgp)^{2}) bit operations.

As with the case of the integers (cf. Algorithm 2.107), the Euclidean algorithm can be extended so that it also yields two polynomials *s(x)* and *t(x)* satisfying

2.221 Algorithm Extended Euclidean algorithm for *Z _{p}[x]*

INPUT: two polynomials *g{x), h(x)* € *Z _{p}[x].*

OUTPUT: *d(x)* = gcd*(g(x),h(x))* and polynomials *s(x), t(x)* € *Z _{p}[x]* which satisfy

*s(x)g(x) + t(x)h(x) = d(x).*

- 1. If
*h(x) =*0 then set*d(x)^g{x),*s(a;)<— 1,*t(x)*0, and remm(d(2:),s(a:),f(a:)). - 2. Set S2(x)<—1, si(x)-t—0, f2(x)-t—0, ti(x)-t— 1.
- 3. While
*h(x) ф*0 do the following: - 3.1
*q(x)<^g(x)*div*h(x), r(x)^g(x)*—*h(x)q(x).* - 3.2
*s(x)**2**(x)*—*q(x)si(x),*<2(2:)^{—}*q(x)ti(x).* - 3.3
*g(x)^li(x),*/i(x)-<—r(x). - 3.4 S2(x)<—si(x), si(x)<—s(x), f2(x)<—
*ti(x),*and*t*(x)-<—*t(x).* - 4. Set
*d(x)**2**{x), t(x)<—t**2**{x).* - 5. Retum(d(x),s(z),t(a:)).
^{[1]}^{[2]}

**Iteration 1**

*q(x) + 1, a;*

^{8}+

*x*+

^{7}*x*+

^{6}+ x^{2}*x,*

*s(x) 1, *

*t(x)<— x*+ 1,

*g(x)t*—*x®* + *x ^{6} + x^{5} + x^{3}* +

*x*1,

^{2}+*h(x)*—x*+

^{&}*x*x

^{7}+^{6}+

*x*+ 1,

^{2}S2(x)<— 0, si(a;)-<— 1, 12(x)<—l, ti(x)<—x+l.

**Iteration 2**

q(x)<— *x* + 1, r(x)-t— x^{5} + *x ^{2}* +

*x*+ 1,

*s(x)<—x*+ 1,

*t(x)<—x*

^{2},*g(x)<—x ^{&} + x‘ + x^{G} + x^{2}* + 1,

*h(x)<—x*+

^{5}+ x^{2}*x*+ 1,

*S**2**(x) 1, *

*Si(x)* 1,

*t*

*2*

*(x)^X +*1,

*ti(x)^x*

^{2}.

**Iteration 3**

*q(x)-^x ^{3}* +

*x*+ 1,

^{2}+ x*r(x)*3 +

*x*+ 1, s(a;)<—

*x*b +

^{4}, t(x)*x*+ a:

^{4}^{3}+

*x*+

^{2}*x +*1,

*g(x)<—x*+

^{5}*x*+ 1,

^{2}+ x*h(x)^x*+

^{3}*x*+ 1,

*S**2**{x) 1, *

*Si(x)<^x*

^{4}, t*2*

*{x)-^x*+

^{2}, ti(x)3*X*+

^{4}*X*+

^{3}*X*+ 1.

^{2}+ X

**Iteration 4**

*q[x)i*—*x ^{2}* + 1,

*r(x)^r-*0,

s(a;)<— x^{6} + *x ^{4}* +

*x*+ 1,

*t(x)<—x*+

^{7}+ x^{6}+ x^{2}+ x + 1, g(x)<—x^{3}*x*+ 1,

*h(x)<—*0,

*S**2**{x) 4, si(x)-^x*

^{6}+ x

^{4}+ x + 1,

*t**2**{x)^x ^{b}* +

*x*+ a;

^{4}^{3}+

*x*+

^{2}*x*+ 1,

*t(x)^x‘ + x*+ 1.

^{6}+ x^{2}+ xHence gcd((/(:c), *h(x)) = x ^{3}* +

*x +*1 and

*(x ^{4})g(x)* + (a:

^{5}+

*x*+ a:

^{4}^{3}+

*x*+ l)/i(a;) = ar

^{2}+ x^{3}+

*x*+ 1. □

- [1] 2.222 Fact (running time of Algorithm 2.221) (i) The polynomials s(x) and t(x) given by Algorithm 2.221 have small degree; that is,they satisfy deg «(ж) < deg h(x) and deg t(x) < deg g(x).
- [2] Suppose that deg g(x) < m and deg h(x) < m. Then Algorithm 2.221 has a runningtime of 0(m2) Zp-operations, or equivalently, 0(m2([gp)2) bit operations. 2.223 Example (extended Euclidean algorithm for polynomials) The following are the steps ofAlgorithm 2.221 with inputs g(x) = a;10 + a;9 + x8 + x6 + xb + x4 + 1 and h(x) =a:9 + a:6 + a:5 + a;3 + x2 + 1 in Z2[a;]. Initialization S2{x)