a polynomial in the input length.

The following two exercises show that the problem of factoring polyno-

mials over F reduces in deterministic polynomial time to the problem of

¬nding roots of polynomials over Zp .

Exercise 21.19. Let g be as in Exercise 21.14. Suppose that S =

{»1 , . . . , »s } is a separating set for g over Zp , and φu ∈ F [X] is the min-

imal polynomial over F of [»u ]g ∈ F [X]/(g) for u = 1, . . . , s. Show that each

φu is the product of linear factors over Zp , and that given S along with

the roots of all the φu , we can deterministically factor g using (|S| + )O(1)

operations in F . Hint: see Exercise 17.9.

Exercise 21.20. Using the previous exercise, show that the problem of fac-

toring a polynomial over a ¬nite ¬eld F reduces in deterministic polynomial

time to the problem of ¬nding roots of polynomials over the prime ¬eld of F .

21.6 Faster square-free decomposition (—)

The algorithm presented in §21.4.1 for square-free decomposition was simple

and suitable for our immediate purposes, but is certainly not the most e¬-

cient algorithm possible. The following exercises develop a faster algorithm

for this problem.

We begin with an exercise that more fully develops the connection be-

486 Algorithms for ¬nite ¬elds

tween square-free polynomials and formal derivatives for polynomials over

arbitrary ¬elds:

Exercise 21.21. Let K be a ¬eld, and let f ∈ K[X] with deg(f ) > 0.

(a) Show that if D(f ) = 0, then the characteristic of K must be a prime

p, and f must be of the form f = g(Xp ) for some g ∈ K[X].

(b) Show that if K is a ¬nite ¬eld or a ¬eld of characteristic zero, then

f is square-free if and only if d := gcd(f, D(f )) = 1; moreover, if

d = 1, then either deg(d) < deg(f ), or K has prime characteristic p

and f = hp for some h ∈ K[X].

(c) Give an example of a ¬eld K of characteristic p and an irreducible

polynomial f ∈ K[X] such that f = g(Xp ) for some g ∈ K[X].

Next, we consider the problem of square-free decomposition of polynomi-

als over ¬elds of characteristic zero, which is simpler than the corresponding

problem over ¬nite ¬elds.

Exercise 21.22. Let f ∈ K[X] be a monic polynomial over a ¬eld K of

characteristic zero. Suppose that the factorization of f into irreducibles is

e e

f = f1 1 · · · fr r .

Show that

f

= f1 · · · fr .

gcd(f, D(f ))

Exercise 21.23. Let K be a ¬eld of characteristic zero. Consider the fol-

lowing algorithm that takes as input a monic polynomial f ∈ K[X] of degree

> 0:

j ← 1, g ← f / gcd(f, D(f ))

repeat

f ← f /g, h ← gcd(f, g), m ← g/h

if m = 1 then output (m, j)

g ← h, j ← j + 1

until g = 1

Using the result of the previous exercise, show that this algorithm outputs

s

a list of pairs (gi , si ), such that each gi is square-free, f = i gi i , and the gi

are pairwise relatively prime. Furthermore, show that this algorithm uses

O( 2 ) operations in K.

We now turn our attention to square-free decomposition over ¬nite ¬elds.

21.7 Notes 487

Exercise 21.24. Let f ∈ F [X] be a monic polynomial over F (which, as

usual, has characteristic p and cardinality q = pw ). Suppose that the fac-

torization of f into irreducibles is

e e

f = f1 1 · · · fr r .

Show that

f

= fi .

gcd(f, D(f ))

1¤i¤r

ei ≡0 (mod p)

Exercise 21.25. Consider the following algorithm that takes as input a

monic polynomial f ∈ F [X] of degree > 0:

s←1

repeat

j ← 1, g ← f / gcd(f, D(f ))

repeat

f ← f /g, h ← gcd(f, g), m ← g/h

if m = 1 then output (m, js)

g ← h, j ← j + 1

until g = 1

if f = 1 then // f is a pth power

// we compute a pth root as in Algorithm SFD

f ← f 1/p , s ← ps

until f = 1

Using the result of the previous exercise, show that this algorithm outputs

s

a list of pairs (gi , si ), such that each gi is square-free, f = i gi i , and the gi

are pairwise relatively prime. Furthermore, show that this algorithm uses

O( 2 + (w ’ 1) len(p)/p) operations in F .

21.7 Notes

The average-case analysis of Algorithm IPT, assuming its input is random,

and the application to the analysis of Algorithm RIP, is essentially due to

Ben-Or [14]. If one implements Algorithm RIP using fast polynomial arith-

metic, one gets an expected cost of O( 2+o(1) len(q)) operations in F . Note

that Ben-Or™s analysis is a bit incomplete”see Exercise 32 in Chapter 7 of

Bach and Shallit [12] for a complete analysis of Ben-Or™s claims.

The asymptotically fastest probabilistic algorithm for constructing an ir-

reducible polynomial over F of degree is due to Shoup [91]. That algorithm

uses an expected number of O( 2+o(1) + 1+o(1) len(q)) operations in F , and

488 Algorithms for ¬nite ¬elds

in fact does not follow the “generate and test” paradigm of Algorithm RIP,

but uses a completely di¬erent approach. Exercise 21.2 is based on [91].

As far as deterministic algorithms for constructing irreducible polynomials

of given degree over F , the only known methods are e¬cient when the

characteristic p of F is small (see Chistov [26], Semaev [83], and Shoup

[89]), or under a generalization of the Riemann hypothesis (see Adleman and

Lenstra [4]). Shoup [89] in fact shows that the problem of constructing an

irreducible polynomial of given degree over F is deterministic, polynomial-

time reducible to the problem of factoring polynomials over F .

The algorithm in §21.2 for computing minimal polynomials over ¬nite

¬elds is due to Gordon [41].

The Cantor“Zassenhaus algorithm was initially developed by Cantor and

Zassenhaus [24], although many of the basic ideas can be traced back quite

a ways. A straightforward implementation of this algorithm using fast poly-

nomial arithmetic uses an expected number of O( 2+o(1) len(q)) operations

in F .

Berlekamp™s algorithm was initially developed by Berlekamp [15, 16],

but again, the basic ideas go back a long way. A straightforward imple-

mentation using fast polynomial arithmetic uses an expected number of

O( 3 + 1+o(1) len(q)) operations in F ; the term 3 may be replaced by ω ,

where ω is the exponent of matrix multiplication (see §15.6).

There are no known e¬cient, deterministic algorithms for factoring poly-

nomials over F when the characteristic p of F is large (even under a gener-

alization of the Riemann hypothesis, except in certain special cases).

The square-free decomposition of a polynomial over a ¬eld K of character-

istic zero can be computed using an algorithm of Yun [105] using O( 1+o(1) )

operations in K. Yun™s algorithm can be adapted to work over ¬nite ¬elds

as well (see Exercise 14.30 in von zur Gathen and Gerhard [37]).

The asymptotically fastest algorithms for factoring polynomials over a

¬nite ¬eld F are due to von zur Gathen, Kaltofen, and Shoup: the algorithm

of von zur Gathen and Shoup [38] uses an expected number of O( 2+o(1) +

1+o(1) len(q)) operations in F ; the algorithm of Kaltofen and Shoup [51]

has a cost that is subquadratic in the degree ” it uses an expected number

of O( 1.815 len(q)0.407 ) operations in F . Exercises 21.1, 21.7, and 21.8 are