¤2 + len(q) deg(h) = O( len(q)).

h∈H

• The expected number of iterations of the main loop until we get some

non-trivial split is O(1).

482 Algorithms for ¬nite ¬elds

• The algorithm ¬nishes after getting r ’ 1 non-trivial splits.

• Therefore, the total expected cost is O(r 2 len(q)) operations in F .

A more careful analysis reveals:

Theorem 21.10. Algorithm B2 uses an expected number of

2

O(len(r) len(q))

operations in F .

Proof. The proof follows the same line of reasoning as the analysis of Al-

gorithm EDF. Indeed, using the same argument as was used there, the

expected number of iterations of the main loop is O(len(r)). As discussed in

the paragraph above this theorem, the cost per loop iteration is O( 2 len(q))

operations in F . The theorem follows. 2

The bound in the above theorem is tight (see Exercise 21.11 below): unlike

Algorithm EDF, we cannot make the multiplicative factor of len(r) go away.

21.4.3 Analysis of the whole algorithm

Putting together Algorithm SFD with algorithms B1 and B2, we get

Berlekamp™s complete factoring algorithm. The running time bound is easily

estimated from the results already proved:

Theorem 21.11. Berlekamp™s factoring algorithm uses an expected number

of O( 3 + 2 len( ) len(q)) operations in F .

So we see that Berlekamp™s algorithm is in fact faster than the Cantor“

Zassenhaus algorithm, whose expected operation count is O( 3 len(q)). The

speed advantage of Berlekamp™s algorithm grows as q gets large. The one

disadvantage of Berlekamp™s algorithm is space: it requires space for ˜( 2 )

elements of F , while the Cantor“Zassenhaus algorithm requires space for

only O( ) elements of F . One can in fact implement the Cantor“Zassenhaus

algorithm so that it uses O( 3 + 2 len(q)) operations in F , while using space

for only O( 1.5 ) elements of F ”see Exercise 21.13 below.

Exercise 21.10. Give an example of a family of input polynomials f that

cause Algorithm SFD to use at least „¦( 3 ) operations in F , where :=

deg(f ).

Exercise 21.11. Give an example of a family of input polynomials f that

cause Algorithm B2 to use an expected number of at least „¦( 2 len( ) len(q))

operations in F , where := deg(f ).

21.5 Deterministic factorization algorithms (—) 483

Exercise 21.12. Using the ideas behind Berlekamp™s factoring algorithm,

devise a deterministic irreducibility test that, given a monic polynomial of

degree over F , uses O( 3 + 2 len(q)) operations in F .

Exercise 21.13. This exercise develops a variant of the Cantor“Zassenhaus

algorithm that uses O( 3 + 2 len(q)) operations in F , while using space for

only O( 1.5 ) elements of F . By making use of Algorithm SFD (which with

a bit of care can be implemented so as to use space for O( ) elements of F )

and the variant of Algorithm EDF discussed in Exercise 21.8, our problem

is reduced to that of implementing Algorithm DDF within the stated time

and space bounds, assuming that the input polynomial is square-free.

(a) For non-negative integers i, j, with i = j, show that the irreducible

i j

polynomials in F [X] that divide Xq ’ Xq are precisely those whose

degree divides i ’ j.

1/2 .

(b) Let f ∈ F [X] be a monic polynomial of degree > 0, and let m ≈

Let · := [X]f ∈ E, where E := F [X]/(f ). Show how to compute

2 m’1 m 2m (m’1)m

·q , ·q , . . . , ·q ∈ E and · q , · q , . . . , ·q ∈E

using O( 3 + 2 len(q)) 1.5 )

operations in F , and space for O( elements

of F .

(c) Combine the results of parts (a) and (b) to implement Algorithm

DDF on square-free inputs of degree , so that it uses O( 3 + 2 len(q))

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

21.5 Deterministic factorization algorithms (—)

The algorithms of Cantor and Zassenhaus and of Berlekamp are probabilis-

tic. The exercises below develop a deterministic variant of the Cantor“

Zassenhaus algorithm. (One can also develop deterministic variants of

Berlekamp™s algorithm, with similar complexity.)

This algorithm is only practical for ¬nite ¬elds of small characteristic, and

is anyway mainly of theoretical interest, since from a practical perspective,

there is nothing wrong with the above probabilistic method. In all of these

exercises, we assume that we have access to a basis 1 , . . . , w for F as a

vector space over Zp .

To make the Cantor“Zassenhaus algorithm deterministic, we only need

to develop a deterministic variant of Algorithm EDF, as Algorithm DDF is

already deterministic.

484 Algorithms for ¬nite ¬elds

Exercise 21.14. Let g = g1 · · · gr , where the gi are distinct monic irre-

ducible polynomials in F [X]. Assume that r > 1, and let := deg(g). For

this exercise, the degrees of the gi need not be the same. For an intermediate

¬eld F , with Zp ⊆ F ⊆ F , let us call a set S = {»1 , . . . , »s } of polynomials

in F [X]< a separating set for g over F if the following conditions hold:

• for i = 1, . . . , r and u = 1, . . . , s, there exists cui ∈ F such that

»u ≡ cui (mod gi ), and

• for any distinct pair of indices i, j, with 1 ¤ i < j ¤ r, there exists

u = 1, . . . , s such that cui = cuj .

Show that if S is a separating set for g over Zp , then the following algorithm

completely factors g using O(p|S| 2 ) operations in F .

H ← {g}

for each » ∈ S do

for each a ∈ Zp do

H ←…

for each h ∈ H do

d ← gcd(» ’ a, h)

if d = 1 or d = h

then H ← H ∪ {h}

else H ← H ∪ {d, h/d}

H←H

output H

Exercise 21.15. Let g be as in the previous exercise. Show that if S is a

separating set for g over F , then the set

w’1

i

( j »)p mod g : 1 ¤ j ¤ w, » ∈ S}

S := {

i=0

is a separating set for g over Zp . Show how to compute this set using

O(|S| 2 len(p)w(w ’ 1)) operations in F .

Exercise 21.16. Let g be as in the previous two exercises, but further

suppose that each irreducible factor of g is of the same degree, say k. Let

E := F [X]/(g) and · := [X]g ∈ E. De¬ne the polynomial φ ∈ E[Y] as follows:

k’1

i

(Y ’ · q ).

φ :=

i=0

If

φ = Yk + ±k’1 Yk’1 + · · · + ±0 ,

21.6 Faster square-free decomposition (—) 485

with ±0 , . . . , ±k’1 ∈ E, show that the set

S := {rep(±i ) : 0 ¤ i ¤ k ’ 1}

is a separating set for g over F , and can be computed deterministically using

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

in F .

Exercise 21.17. Put together all of the above pieces, together with Algo-

rithm DDF, so as to obtain a deterministic algorithm for factoring polyno-

mials over F that runs in time at most p times a polynomial in the input

length, and make a careful estimate of the running time of your algorithm.

Exercise 21.18. It is a fact that when our prime p is odd, then for all

integers a, b, with a ≡ b (mod p), there exists a non-negative integer

i ¤ p1/2 log2 p such that (a + i | p) = (b + i | p) (here, “(· | ·)” is the

Legendre symbol). Using this fact, design and analyze a deterministic algo-