Berlekamp [15] and Massey [60] discuss an algorithm for ¬nding the mini-

mal polynomial of a linearly generated sequence that is closely related to the

one presented in §19.2, and which has a similar complexity. This connection

between Euclid™s algorithm and ¬nding minimal polynomials of linearly gen-

erated sequences has been observed by many authors, including Mills [64],

Welch and Scholtz [102], and Dornstetter [35].

The algorithm presented in §19.3, is due to Wiedemann [103], as are the

algorithms for solving sparse linear systems in §19.4, as well as the statement

and proof outline of the result in Exercise 19.18.

Our proof of Theorem 19.5 is based on an exposition by Morrison [65].

Using fast matrix and polynomial arithmetic, Shoup [91] shows how to

implement the algorithms in §19.5 so as to use just O( (ω+1)/2 ) operations

in F , where ω is the exponent for matrix multiplication (see §15.6), and so

(ω + 1)/2 < 1.7.

20

Finite ¬elds

This chapter develops some of the basic theory of ¬nite ¬elds. As we already

know (see Theorem 9.7), every ¬nite ¬eld must be of cardinality pw , for some

prime p and positive integer w. The main results of this chapter are:

• for any prime p and positive integer w, there exists a ¬nite ¬eld of

cardinality pw , and

• any two ¬nite ¬elds of the same cardinality are isomorphic.

20.1 Preliminaries

In this section, we prove a few simple facts that will be useful in this and

later chapters; also, for the reader™s convenience, we recall a few basic alge-

braic concepts that were discussed in previous chapters, but which will play

important roles in this chapter.

Theorem 20.1. Let F be a ¬eld, and let k, be positive integers. Then

Xk ’ 1 divides X ’ 1 if and only if k divides .

= kq + r, with 0 ¤ r < k. We have

Proof. Let

X ≡ Xkq Xr ≡ Xr (mod Xk ’ 1),

and Xr ≡ 1 (mod Xk ’ 1) if and only if r = 0. 2

Theorem 20.2. Let a ≥ 2 be an integer and let k, be positive integers.

Then ak ’ 1 divides a ’ 1 if and only if k divides .

Proof. The proof is analogous to that of Theorem 20.1. We leave the details

to the reader. 2

One may combine these two theorems, obtaining:

448

20.1 Preliminaries 449

Theorem 20.3. Let a ≥ 2 be an integer, k, be positive integers, and F a

k

¬eld. Then Xa ’ X divides Xa ’ X if and only if k divides .

k k

Proof. We have Xa ’ X divides Xa ’ X i¬ Xa ’1 ’ 1 divides Xa ’1 ’ 1, and by

Theorem 20.1, this happens i¬ ak ’ 1 divides a ’ 1, which by Theorem 20.2

happens i¬ k divides . 2

Let F be a ¬eld. A polynomial f ∈ F [X] is called square-free if it is not

divisible by the square of any polynomial of degree greater than zero. Using

formal derivatives, we obtain the following useful criterion for establishing

that a polynomial is square-free:

Theorem 20.4. If F is a ¬eld, and f ∈ F [X] with gcd(f, D(f )) = 1, then

f is square-free.

Proof. Suppose f is not square-free, and write f = g 2 h, for g, h ∈ F [X] with

deg(g) > 0. Taking formal derivatives, we have

D(f ) = 2gD(g)h + g 2 D(h),

and so clearly, g is a common divisor of f and D(f ). 2

We end this section by recalling some concepts discussed earlier, mainly

in §17.1, §17.5, and §17.6.

Suppose F is a ¬eld, and E is an extension ¬eld of F ; that is, F is a

sub¬eld of E, or F is embedded in E via some canonical embedding, and

we identify elements of F with their images in E under this embedding. We

may naturally view E as an F -vector space. Assume that as an F -vector

space, E has ¬nite dimension > 0. This dimension is called the degree

of E over F , and is denoted (E : F ); moreover, E is called a ¬nite extension

of F .

We may also naturally view E as an F -algebra, either via the inclusion

map or via some canonical embedding. Let E be another ¬eld extension

of F , and let ρ : E ’ E be a ring homomorphism (which in fact, must be

injective). Then ρ is an F -algebra homomorphism if and only if ρ(a) = a

for all a ∈ F .

For any ± ∈ E, the set F [±] = {g(±) : g ∈ F [X]} is a sub¬eld of E

containing F . Moreover, there exists a non-zero polynomial g of degree at

most such that g(±) = 0. The monic polynomial φ of least degree such that

φ(±) = 0 is called the minimal polynomial of ± over F , and this polynomial

is irreducible over F . The ¬eld F [X]/(φ) is isomorphic, as an F -algebra,

to F [±], via the map that sends [g]φ ∈ F [X]/(φ) to g(±) ∈ F [±]. We have

(F [±] : F ) = deg(φ), and this value is called the degree of ± over F . If E is

450 Finite ¬elds

an extension ¬eld of F , and if ρ : F [±] ’ E is an F -algebra homomorphism,

then the action of ρ is completely determined by its action on ±; indeed, for

any g ∈ F [X], we have ρ(g(±)) = g(ρ(±)).

20.2 The existence of ¬nite ¬elds

Let F be a ¬nite ¬eld. As we saw in Theorem 9.7, F must have cardinality

pw , where p is prime and w is a positive integer, and p is the characteristic of

F . However, we can say a bit more than this. As discussed in Example 9.41,

the ¬eld Zp is embedded in F , and so we may simply view Zp as a sub¬eld

of F . Moreover, it must be the case that w is equal to (F : Zp ).

We want to show that there exist ¬nite ¬elds of every prime-power cardi-

nality. Actually, we shall prove a more general result:

≥ 1, there exists

If F is a ¬nite ¬eld, then for every integer

an extension ¬eld E of degree over F .

For the remainder of this section, F denotes a ¬nite ¬eld of cardinality

q = pw , where p is prime and w ≥ 1.

Suppose for the moment that E is an extension of degree over F . Let

us derive some basic facts about E. First, observe that E has cardinality

q . By Theorem 9.16, E — is cyclic, and the order of E — is q ’ 1. If γ ∈ E —

is a generator for E — , then every non-zero element of E can be expressed

as a power of γ; in particular, every element of E can be expressed as a

polynomial in γ with coe¬cients in F ; that is, E = F [γ]. Let φ ∈ F [X] be

the minimal polynomial of γ over F , which is an irreducible polynomial of

degree . It follows that F is isomorphic (as an F -algebra) to F [X]/(φ).

So we have shown that any extension of F of degree must be isomorphic,

as an F -algebra, to F [X]/(φ) for some irreducible polynomial φ ∈ F [X] of

degree . Conversely, given any irreducible polynomial φ over F of degree ,

we can construct the ¬nite ¬eld F [X]/(φ), which has degree over F . Thus,

the question of the existence of a ¬nite ¬elds of degree over F reduces to

the question of the existence of an irreducible polynomial over F of degree .

We begin with a simple generalization Fermat™s little theorem:

Theorem 20.5. For any a ∈ F — , we have aq’1 = 1, and for any a ∈ F , we

have aq = a.

Proof. The multiplicative group of units F — of F has order q ’ 1, and hence,

every a ∈ F — satis¬es the equation aq’1 = 1. Multiplying this equation by

a yields aq = a for all a ∈ F — , and this latter equation obviously holds for

a = 0 as well. 2

20.2 The existence of ¬nite ¬elds 451

Theorem 20.6. We have

Xq ’ X = (X ’ a).

a∈F

Proof. The polynomial

(Xq ’ X) ’ (X ’ a)

a∈F

has degree less than q, but has q distinct roots (namely, every element of

F ), and hence must be the zero polynomial. 2

The following theorem generalizes Example 17.6:

Theorem 20.7. Let E be an F -algebra. Then the map ρ : E ’ E that

sends ± ∈ E to ±q is an F -algebra homomorphism.