Theorem 21.6. The Cantor“Zassenhaus factoring algorithm uses an ex-

pected number of O( 3 len(q)) operations in F .

This bound is tight, since in the worst case, when the input is irreducible,

the algorithm really does do this much work.

Exercise 21.6. Show how to modify Algorithm DDF so that the main loop

halts as soon as 2k > deg(f ).

21.4 Factoring polynomials: Berlekamp™s algorithm 475

Exercise 21.7. This exercise extends the techniques developed in Exer-

cise 21.1. Let f ∈ F [X] be a monic polynomial of degree > 0, and let

· := [X]f ∈ E, where E := F [X]/(f ). For integer m > 0, de¬ne polynomials

m’1 m’1

Tm := X + Xq + · · · + Xq ∈ F [X] and Nm := X · Xq · · · · · Xq ∈ F [X].

m m

(a) Show how to compute ” given as input · q ∈ E and · q , where m

and m are positive integers, along with Tm (±) and Tm (±), for some

m+m

± ∈ E ” the values · q and Tm+m (±), using O( 2.5 ) operations

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

(b) Using part (a), show how to compute ” given as input · q ∈ E, ± ∈

E, and a positive integer m ” the value Tm (±), using O( 2.5 len(m))

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

(c) Repeat parts (a) and (b), except with “N ” in place of “T .”

Exercise 21.8. Using the result of the previous exercise, show how to im-

plement Algorithm EDF so that it uses an expected number of

2.5 2

O(len(k) + len(q))

1.5 )

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

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

Let E be an extension ¬eld of degree over F , speci¬ed by an irreducible

polynomial of degree over F . Design and analyze an e¬cient probabilis-

tic algorithm that ¬nds a normal basis for E over F (see Exercise 20.14).

Hint: there are a number of approaches to solving this problem; one way

is to start by factoring X ’ 1 over F , and then turn the construction in

Theorem 19.7 into an e¬cient probabilistic procedure; if you mimic Ex-

ercise 11.2, your entire algorithm should use O( 3 len( ) len(q)) operations

in F (or O(len(r) 3 len(q)) operations, where r is the number of distinct

irreducible factors of X ’ 1 over F ).

21.4 Factoring polynomials: Berlekamp™s algorithm

We now develop an alternative algorithm, due to Berlekamp, for factoring

a polynomial over the ¬nite ¬eld F .

This algorithm usually starts with a pre-processing phase to reduce the

problem to that of factoring square-free polynomials. There are a number

of ways to carry out this step. We present a simple-minded method here

that is su¬cient for our purposes.

476 Algorithms for ¬nite ¬elds

21.4.1 A simple square-free decomposition algorithm

Let f ∈ F [X] be a monic polynomial of degree > 0. Suppose that f is

not square-free. According to Theorem 20.4, d := gcd(f, D(f )) = 1, and

so we might hope to get a non-trivial factorization of f by computing d;

however, we have to consider the possibility that d = f . Can this happen?

The answer is “yes,” but if it does happen that d = f , we can still get a

non-trivial factorization of f by other means:

Theorem 21.7. Suppose that f ∈ F [X] is a polynomial of degree > 0, and

that gcd(f, D(f )) = f . Then f = g(Xp ) for some g ∈ F [X]. Moreover, if

p(w’1) i

g = i bi Xi , then f = hp , where h = i bi X.

Proof. Since deg(D(f )) < deg(f ), if gcd(f, D(f )) = f , then we must have

D(f ) = 0. If f = i=0 ai Xi , then D(f ) = i=1 iai Xi’1 . Since this deriva-

tive must be zero, it follows that all the coe¬cients ai with i ≡ 0 (mod p)

must be zero to begin with. That proves that f = g(Xp ) for some g ∈ F [X].

Furthermore, if h is de¬ned as above, then

p

(w’1) w

bp bp Xip = bi (Xp )i = g(Xp ) = f. 2

p

Xi

h= =

i i

i i i

This suggests the following recursive algorithm. The input is the polyno-

mial f as above, and a parameter s, which is set to 1 on the initial invoca-

tion. The output is a list of pairs (gi , si ) such that each gi is a square-free,

s

non-constant polynomial over F and f = i gi i .

Algorithm SFD:

d ← gcd(f, D(f ))

if d = 1 then

output (f, s)

else if d = f then

recursively process (d, s) and (f /d, s)

else

’1

let f = X + i=0 ai Xi // note that ai = 0 except when p | i

/p’1 w’1

set h ← X /p + i=0 (api )p Xi // note that h = f 1/p

recursively process (h, ps)

The correctness of Algorithm SFD follows from the discussion above. As

for its running time:

3 + (w ’ 1) len(p)/p) operations

Theorem 21.8. Algorithm SFD uses O(

in F .

21.4 Factoring polynomials: Berlekamp™s algorithm 477

Proof. For input polynomial f with deg(f ) > 0, let R(f ) denote the number

of recursive invocations of the algorithm, and let P (f ) denote the number

of pw’1 th powers in F computed by the algorithm. It is easy to see that the

number of operations in F performed by the algorithm is

O(R(f ) deg(f )2 + P (f )(w ’ 1) len(p)).

The theorem will therefore follow from the following two inequalities:

R(f ) ¤ 2 deg(f ) ’ 1 (21.4)

and

P (f ) ¤ 2 deg(f )/p. (21.5)

We prove (21.4) by induction of deg(f ). We assume (21.4) holds for all

input polynomials of degree less than that of f , and prove that it holds for

f . Let d := gcd(f, D(f )). If d = 1, then R(f ) = 1 ¤ 2 deg(f ) ’ 1. If d = 1

and d = f , then applying the induction hypothesis, we have

R(f ) = 1 + R(d) + R(f /d) ¤ 1 + (2 deg(d) ’ 1) + (2 deg(f /d) ’ 1)

= 2 deg(f ) ’ 1.

Finally, if d = f , then again applying the induction hypothesis, we have

R(f ) = 1 + R(f 1/p ) ¤ 1 + (2 deg(f )/p ’ 1) ¤ deg(f ) ¤ 2 deg(f ) ’ 1.

The inequality (21.5) is proved similarly by induction. We assume (21.5)

holds for all input polynomials of degree less than that of f , and prove that

it holds for f . Let d := gcd(f, D(f )). If d = 1, then P (f ) = 0 ¤ 2 deg(f )/p.

If d = 1 and d = f , then applying the induction hypothesis, we have

P (f ) = P (d) + P (f /d) ¤ 2 deg(d)/p + 2 deg(f /d)/p = 2 deg(f )/p.

Finally, if d = f , then again applying the induction hypothesis, we have

P (f ) = deg(f )/p + P (f 1/p ) ¤ deg(f )/p + 2 deg(f )/p2 ¤ 2 deg(f )/p. 2

The running-time bound in Theorem 21.8 is essentially tight (see Exer-

cise 21.10 below). Although it su¬ces for our immediate purpose as a pre-

processing step in Berlekamp™s factoring algorithm, Algorithm SFD is by no

means the most e¬cient algorithm possible for square-free decomposition of

polynomials. We return to this issue below, in §21.6.

478 Algorithms for ¬nite ¬elds

21.4.2 The main factoring algorithm

Let us now assume we have a monic square-free polynomial f of degree > 0

that we want to factor into irreducibles, such as is output by the square-free

decomposition algorithm above. We ¬rst present the mathematical ideas

underpinning the algorithm.

Let E be the F -algebra F [X]/(f ). We de¬ne a subset B of E as follows:

B := {± ∈ E : ±q = ±}.

It is easy to see that B is a subalgebra of E. Indeed, for ±, β ∈ B, we have

(±+β)q = ±q +β q = ±+β, and similarly, (±β)q = ±q β q = ±β. Furthermore,

one sees that cq = c for all c ∈ F , and hence B is a subalgebra.

The subalgebra B is called the Berlekamp subalgebra of E. Let us