m+m

m and m are positive integers ”the value · q ∈ E, using O( 2.5 )

operations in F , and space for O( 1.5 ) elements of F .

(c) Show how to compute ”given as input · q ∈ E and a positive integer

m

m ” the value · q ∈ E, using O( 2.5 len(m)) operations in F , and

21.2 Computing minimal polynomials in F [X]/(f ) (III) 465

1.5 )

space for O( elements of F . Hint: use a repeated-squaring-like

algorithm.

Exercise 21.2. This exercise develops an alternative irreducibility test.

(a) Show that a monic polynomial f ∈ F [X] of degree > 0 is irreducible

/s

if and only if Xq ≡ X (mod f ) and gcd(Xq ’ X, f ) = 1 for all primes

s| .

(b) Using part (a) and the result of the previous exercise, show how

to determine if f is irreducible using O( 2.5 len( )ω( ) + 2 len(q))

operations in F , where ω( ) is the number of distinct prime factors

of .

(c) Show that the operation count in part (b) can be reduced to

O( 2.5 len( ) len(ω( )) + 2 len(q)). Hint: see Exercise 3.30.

Exercise 21.3. Design and analyze a deterministic algorithm that takes as

input a list of irreducible polynomials f1 , . . . , fr ∈ F [X], where i := deg(fi )

for i = 1, . . . , r. Assuming that the degrees 1 , . . . , r are pairwise relatively

prime, your algorithm should output an irreducible polynomial f ∈ F [X] of

degree := r 3

i=1 i using O( ) operations in F .

Exercise 21.4. Design and analyze a probabilistic algorithm that, given

a monic irreducible polynomial f ∈ F [X] of degree as input, generates

as output a random monic irreducible polynomial g ∈ F [X] of degree

(i.e., g should be uniformly distributed over all such polynomials), using an

expected number of O( 2.5 ) operations in F . Hint: use Exercise 19.8 (or

alternatively, Exercise 19.9).

Exercise 21.5. Let f ∈ F [X] be a monic irreducible polynomial of degree ,

let E := F [X]/(f ), and let · := [X]f ∈ E. Design and analyze a deterministic

algorithm that takes as input the polynomial f de¬ning the extension E,

and outputs the values

sj := TrE/F (· j ) ∈ F (j = 0, . . . , ’ 1),

using O( 2 ) operations in F . Here, TrE/F is the trace from E to F

(see §20.4). Show that given an arbitrary ± ∈ E, along with the values

s0 , . . . , s ’1 , one can compute TrE/F (±) using just O( ) operations in F .

21.2 Computing minimal polynomials in F [X]/(f ) (III)

We consider, for the third and ¬nal time, the problem considered in §18.2

and §19.5: f ∈ F [X] is a monic polynomial of degree > 0, and E :=

466 Algorithms for ¬nite ¬elds

F [X]/(f ) = F [·], where · := [X]f ; we are given an element ± ∈ E, and

want to compute the minimal polynomial φ ∈ F [X] of ± over F . We develop

an alternative algorithm, based on the theory of ¬nite ¬elds. Unlike the

algorithms in §18.2 and §19.5, this algorithm only works when F is ¬nite

and the polynomial f is irreducible, so that E is also a ¬nite ¬eld.

From Theorem 20.15, we know that the degree of ± over F is the smallest

k

positive integer k such that ±q = ±. By successive qth powering, we can

compute the conjugates of ±, and determine the degree k, using O(k len(q))

operations in E, and hence O(k 2 len(q)) operations in F .

Now, we could simply compute the minimal polynomial φ by directly

using the formula

k’1

i

(Y ’ ±q ).

φ(Y) = (21.1)

i=0

This would involve computations with polynomials in the variable Y whose

coe¬cients lie in the extension ¬eld E, although at the end of the compu-

tation, we would end up with a polynomial all of whose coe¬cients lie in

F . The cost of this approach would be O(k 2 ) operations in E, and hence

O(k 2 2 ) operations in F .

A more e¬cient approach is the following. Substituting · for Y in the

identity (21.1), we have

k’1

i

(· ’ ±q ).

φ(·) =

i=0

Using this formula, we can compute (given the conjugates of ±) the value

φ(·) ∈ E using O(k) operations in E, and hence O(k 2 ) operations in F .

Now, φ(·) is an element of E, and for computational purposes, it is repre-

sented as [g]f for some polynomial g ∈ F [X] of degree less than . Moreover,

φ(·) = [φ]f , and hence φ ≡ g (mod f ). In particular, if k < , then g = φ;

otherwise, if k = , then g = φ ’ f . In either case, we can recover φ from g

with an additional O( ) operations in F .

Thus, given the conjugates of ±, we can compute φ using O(k 2 ) opera-

tions in F . Adding in the cost of computing the conjugates, this gives rise to

an algorithm that computes the minimal polynomial of ± using O(k 2 len(q))

operations in F .

In the worst case, then, this algorithm uses O( 3 len(q)) operations in

F . A reasonably careful implementation needs space for storing a constant

number of elements of E, and hence O( ) elements of F . For very small

values of q, the e¬ciency of this algorithm will be comparable to that of

21.3 Factoring polynomials: the Cantor“Zassenhaus algorithm 467

the algorithm in §19.5, but for large q, it will be much less e¬cient. Thus,

this approach does not really yield a better algorithm, but it does serve to

illustrate some of the ideas of the theory of ¬nite ¬elds.

21.3 Factoring polynomials: the Cantor“Zassenhaus algorithm

In the remaining sections of this chapter, we develop e¬cient algorithms for

factoring polynomials over the ¬nite ¬eld F .

The algorithm we discuss in this section is due to Cantor and Zassenhaus.

It has two stages:

Distinct Degree Factorization: The input polynomial is decomposed

into factors so that each factor is a product of distinct irreducibles

of the same degree (and the degree of those irreducibles is also de-

termined).

Equal Degree Factorization: Each of the factors produced in the dis-

tinct degree factorization stage are further factored into their irre-

ducible factors.

The algorithm we present for distinct degree factorization is a determinis-

tic, polynomial-time algorithm. The algorithm we present for equal degree

factorization is a probabilistic algorithm that runs in expected polynomial

time (and whose output is always correct).

21.3.1 Distinct degree factorization

The problem, more precisely stated, is this: given a monic polynomial f ∈

F [X] of degree > 0, produce a list of polynomial/integer pairs (g, k), where

• each g is a product of distinct monic irreducible polynomials of degree

k, and

• the product of all the polynomials g in the list is equal to f .

This problem can be easily solved using Theorem 20.9, using a simple

variation of the algorithm we discussed in §21.1 for irreducibility testing.

The basic idea is this. We can compute g := gcd(Xq ’ X, f ), so that g is the

product of all the distinct linear factors of f . We can remove the factor g

from f , but after doing so, f may still contain some linear factors (if the

original polynomial was not square-free), and so we have to repeat the above

step until no linear factors are discovered. Having removed all linear factors

2

from f , we next compute gcd(Xq ’ X, f ), which will be the product of all

the distinct quadratic irreducibles dividing f , and we can remove these from

2

f ” although Xq ’ X is the product of all linear and quadratic irreducibles,

468 Algorithms for ¬nite ¬elds

since we have already removed the linear factors from f , the gcd will give us

just the quadratic factors of f . As above, we may have to repeat this a few

times to remove all the quadratic factors from f . In general, for k = 1, . . . , ,

having removed all the irreducible factors of degree less than k from f , we

k

compute gcd(Xq ’ X, f ) to obtain the product of all the distinct irreducible