F , then p divides the degree of ± over F .

Exercise 20.10. Let F be a ¬nite ¬eld of characteristic p. For a ∈ F ,

consider the polynomial f := Xq ’ X ’ a ∈ F [X].

(a) Show that if F = Zp and a = 0, then f is irreducible.

(b) More generally, show that if TrF/Zp (a) = 0, then f is irreducible, and

otherwise, f splits into distinct linear factors over F .

Exercise 20.11. Let E be a ¬nite extension of a ¬nite ¬eld F . Let ±, β ∈ E,

where ± has degree a over F , β has degree b over F , and gcd(a, b) = 1. Show

that ± + β has degree ab over F .

Exercise 20.12. Let E be a ¬nite extension of a ¬nite ¬eld F . Show that

any F -algebra automorphism on E must be a power of a the Frobenius map

on E over F .

Exercise 20.13. Show that for all primes p, the polynomial X4 + 1 is re-

ducible in Zp [X]. (Contrast this to the fact that this polynomial is irreducible

in Q[X], as discussed in Exercise 17.39.)

Exercise 20.14. This exercise depends on the concepts and results in §19.6.

Let F be a ¬nite ¬eld and let E be an extension of degree . Let σ be the

Frobenius map on E over F .

(a) Show that the minimal polynomial of σ over F is X ’ 1.

(b) Show that there exists β ∈ E such that the minimal polynomial of β

under σ is X ’ 1.

(c) Conclude that β, σ(β), . . . , σ ’1 (β) is a basis for E over F . This type

of basis is called a normal basis.

21

Algorithms for ¬nite ¬elds

This chapter discusses e¬cient algorithms for factoring polynomials over

¬nite ¬elds, and related problems, such as testing if a given polynomial is

irreducible, and generating an irreducible polynomial of given degree.

Throughout this chapter, F denotes a ¬nite ¬eld of character-

istic p and cardinality q = pw .

In addition to performing the usual arithmetic and comparison operations

in F , we assume that our algorithms have access to the numbers p, w, and

q, and have the ability to generate random elements of F . Generating such

a random ¬eld element will count as one “operation in F ,” along with the

usual arithmetic operations. Of course, the “standard” ways of representing

F as either Zp (if w = 1), or as the ring of polynomials modulo an irreducible

polynomial over Zp of degree w (if w > 1), satisfy the above requirements,

and also allow for the implementation of arithmetic operations in F that

take time O(len(q)2 ) on a RAM (using simple, quadratic-time arithmetic

for polynomials and integers).

21.1 Testing and constructing irreducible polynomials

Let f ∈ F [X] be a monic polynomial of degree > 0. We develop here an

e¬cient algorithm that determines if f is irreducible.

The idea is a simple application of Theorem 20.9. That theorem says that

k

for any integer k ≥ 1, the polynomial Xq ’ X is the product of all monic

irreducibles whose degree divides k. Thus, gcd(Xq ’X, f ) is the product of all

2

the distinct linear factors of f . If f has no linear factors, then gcd(Xq ’X, f )

is the product of all the distinct quadratic irreducible factors of f . And so

on. Now, if f is not irreducible, it must be divisible by some irreducible

polynomial of degree at most /2, and if g is an irreducible factor of f

462

21.1 Testing and constructing irreducible polynomials 463

k

of minimal degree, say k, then we have k ¤ /2 and gcd(Xq ’ X, f ) =

k

1. Conversely, if f is irreducible, then gcd(Xq ’ X, f ) = 1 for all positive

integers k up to /2. So to test if f is irreducible, it su¬ces to check if

k

gcd(Xq ’ X, f ) = 1 for all positive integers k up to /2 ” if so, we may

conclude that f is irreducible, and otherwise, we may conclude that f is

not irreducible. To carry out the computation e¬ciently, we note that if

k k

h ≡ Xq (mod f ), then gcd(h ’ X, f ) = gcd(Xq ’ X, f ).

The above observations suggest the following algorithm, which takes as

input a monic polynomial f ∈ F [X] of degree > 0, and outputs true if f is

irreducible, and false otherwise:

Algorithm IPT:

h ← X mod f

for k ← 1 to /2 do

h ← hq mod f

if gcd(h ’ X, f ) = 1 then return false

return true

The correctness of Algorithm IPT follows immediately from the above

discussion. As for the running time, we have:

3 len(q))

Theorem 21.1. Algorithm IPT uses O( operations in F .

Proof. Consider an execution of a single iteration of the main loop. The cost

of the qth-powering step (using a standard repeated-squaring algorithm) is

O(len(q)) multiplications modulo f , and so O( 2 len(q)) operations in F .

The cost of the gcd computation is O( 2 ) operations in F . Thus, the cost of

a single loop iteration is O( 2 len(q)) operations in F , from which it follows

that the cost of the entire algorithm is O( 3 len(q)) operations in F . 2

Algorithm IPT is a “polynomial time” algorithm, since the length of the

binary encoding of the input is about len(q), and so the algorithm runs in

time polynomial in its input length, assuming that arithmetic operations in

F take time polynomial in len(q). Indeed, using a standard representation

for F , each operation in F takes time O(len(q)2 ) on a RAM, and so the

running time on a RAM for the above algorithm would be O( 3 len(q)3 ),

that is, cubic in the bit-length of the input.

Let us now consider the related problem of constructing an irreducible

polynomial of speci¬ed degree > 0. To do this, we can simply use the

result of Theorem 20.11, which has the following probabilistic interpretation:

if we choose a random, monic polynomial f of degree over F , then the

464 Algorithms for ¬nite ¬elds

probability that f is irreducible is at least 1/2 . This suggests the following

probabilistic algorithm:

Algorithm RIP:

repeat

choose a0 , . . . , a ’1 ∈ F at random

’1

set f ← X + i=0 ai Xi

test if f is irreducible using Algorithm IPT

until f is irreducible

output f

Theorem 21.2. Algorithm RIP uses an expected number of O( 4 len(q))

operations in F , and its output is uniformly distributed over all monic irre-

ducibles of degree .

Proof. Because of Theorem 20.11, the expected number of loop iterations

of the above algorithm is O( ). Since Algorithm IPT uses O( 3 len(q)) op-

erations in F , the statement about the running time of Algorithm RIP is

immediate. The statement about its output distribution is clear. 2

The expected running-time bound in Theorem 21.2 is actually a bit of

an over-estimate. The reason is that if we generate a random polynomial

of degree , it is likely to have a small irreducible factor, which will be

discovered very quickly by Algorithm IPT. In fact, it is known (see §21.7)

that the expected value of the degree of the least degree irreducible factor

of a random monic polynomial of degree over F is O(len( )), from which it

follows that the expected number of operations in F performed by Algorithm

RIP is actually O( 3 len( ) len(q)).

Exercise 21.1. Let f ∈ F [X] be a monic polynomial of degree > 0. Also,

let · := [X]f ∈ E, where E is the F -algebra E := F [X]/(f ).

m

(a) Show how to compute ”given as input ± ∈ E and · q ∈ E (for some

m

integer m > 0)”the value ±q ∈ E, using just O( 2.5 ) operations in

F , and space for O( 1.5 ) elements of F . Hint: see Theorems 17.1 and

20.7, as well as Exercise 18.4.

m m