The above discussion leads to the following algorithm for distinct degree

factorization, which takes as input a monic polynomial f ∈ F [X] of degree

> 0:

Algorithm DDF:

h ← X mod f

k←1

while f = 1 do

h ← hq mod f

g ← gcd(h ’ X, f )

while g = 1 do

output (g, k)

f ← f /g

h ← h mod f

g ← gcd(h ’ X, f )

k ←k+1

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

for the running time:

3 len(q))

Theorem 21.3. Algorithm DDF uses O( operations in F .

Proof. Note that the body of the outer loop is executed at most times,

since after iterations, we will have removed all the factors of f . Thus,

we perform at most qth-powering steps, each of which takes O( 2 len(q))

operations in F , and so the total contribution to the running time of these is

O( 3 len(q)) operations in F . We also have to take into account the cost of

the gcd computations. We perform one gcd computation in every iteration

of the main loop, for a total of such computations. We also perform

an “extra” gcd computation whenever we discover a non-trivial factor of

f ; however, since we only discover at most such non-trivial factors, we

perform at most such “extra” gcd computations. So the total number of

gcd computations is at most 2 , and as each of these takes O( 2 ) operations

in F , they contribute a term of O( 3 ) to the total operation count. This

21.3 Factoring polynomials: the Cantor“Zassenhaus algorithm 469

term is dominated by the cost of the qth-powering steps (as is the cost of

the division step in the inner loop), and so the total cost of Algorithm DDF

is O( 3 len(q)) operations in F . 2

21.3.2 Equal degree factorization

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

F [X] of degree > 0, and an integer k > 0, such that g is of the form

g = g1 · · · gr

for distinct monic irreducible polynomials g1 , . . . , gr , each of degree k, com-

pute these irreducible factors of g. Note that given g and k, the value of r

is easily determined, since r = /k.

We begin by discussing the basic mathematical ideas that will allow us

to e¬ciently split g into two non-trivial factors, and then we present a

somewhat more elaborate algorithm that completely factors g.

By the Chinese remainder theorem, we have an F -algebra isomorphism

θ : E1 — · · · — Er ’ E,

where for i = 1, . . . , r, Ei is the extension ¬eld F [X]/(gi ) of degree k over F ,

and E is the F -algebra F [X]/(g).

Recall that q = pw . We have to treat the cases p = 2 and p > 2 separately.

We ¬rst treat the case p = 2. Let us de¬ne the polynomial

wk’1

j

X2 ∈ F [X].

Mk := (21.2)

j=0

(The algorithm in the case p > 2 will only di¬er in the de¬nition of Mk .)

For ± ∈ E, if ± = θ(±1 , . . . , ±r ), then we have

Mk (±) = θ(Mk (±1 ), . . . , Mk (±r )).

Note that each Ei is an extension of Z2 of degree wk, and that

wk’1

j

2

Mk (±i ) = ±i = TrEi /Z2 (±i ),

j=0

where TrEi /Z2 : Ei ’ Z2 is the trace from Ei to Z2 , which is a surjective,

Z2 -linear map (see §20.4).

Now, suppose we choose ± ∈ E at random. Then if ± = θ(±1 , . . . , ±r ),

the ±i will be independently distributed, with each ±i uniformly distributed

470 Algorithms for ¬nite ¬elds

over Ei . It follows that the values Mk (±i ) will be independently and uni-

formly distributed over Z2 . Thus, if a := rep(Mk (±)) (i.e., a ∈ F [X] is the

polynomial of degree less than such that Mk (±) = [a]g ), then gcd(a, g) will

be the product of those factors gi of g such that Mk (±i ) = 0. We will fail

to get a non-trivial factorization only if the Mk (±i ) are either all 0 or all 1,

which for r ≥ 2 happens with probability at most 1/2 (the worst case being

when r = 2).

That is our basic splitting strategy. The algorithm for completely factor-

ing g works as follows. The algorithm proceeds in stages. At any stage, we

have a partial factorization g = h∈H h, where H is a set of non-constant,

monic polynomials. Initially, H = {g}. With each stage, we attempt to get

a ¬ner factorization of g by trying to split each h ∈ H using the above split-

ting strategy”if we succeed in splitting h into two non-trivial factors, then

we replace h by these two factors. We continue in this way until |H| = r.

Here is the full equal degree factorization algorithm. It takes as input a

monic polynomial g ∈ F [X] of degree > 0, and an integer k > 0, such that

g is the product of r := /k distinct monic irreducible polynomials, each of

degree k. With Mk as de¬ned in (21.2), the algorithm runs as follows:

Algorithm EDF:

H ← {g}

while |H| < r do

H ←…

for each h ∈ H do

choose ± ∈ F [X]/(h) at random

d ← gcd(rep(Mk (±)), h)

if d = 1 or d = h

then H ← H ∪ {h}

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

H←H

output H

The correctness of the algorithm is clear from the above discussion. As

for its expected running time, we can get a quick-and-dirty upper bound as

follows:

• For a given h, the cost of computing Mk (±) for ± ∈ F [X]/(h) is

O(k deg(h)2 len(q)) operations in F , and so the number of operations

in F performed in each iteration of the main loop is at most a constant

21.3 Factoring polynomials: the Cantor“Zassenhaus algorithm 471

times

2

2 2

deg(h) ¤ k len(q)

k len(q) deg(h) =k len(q).

h∈H h∈H

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

non-trivial split is O(1).

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

2 len(q)), 3 len(q)),

• Therefore, the total expected cost is O(rk or O(

operations in F .

This analysis gives a bit of an over-estimate”it does not take into account

the fact that we expect to get fairly “balanced” splits. For the purposes

of analyzing the overall running time of the Cantor“Zassenhaus algorithm,

this bound su¬ces; however, the following analysis gives a tight bound on

the complexity of Algorithm EDF.

Theorem 21.4. In the case p = 2, Algorithm EDF uses an expected number

of O(k 2 len(q)) operations in F .

Proof. We may assume r ≥ 2. Let L be a random variable that denotes the

number of iterations of the main loop of the algorithm.

We claim that E[L] = O(len(r)). To prove this claim, we make use of the

fact (see Theorem 6.25) that

P[L ≥ t].

E[L] =

t≥1

For i = 1, . . . , r and j = i+1, . . . , r, de¬ne Lij to be the number of iterations