beginning of the loop. Now, if gi and gj have not been separated at the

beginning of one loop iteration, then they will be separated at the beginning

of the next with probability 1/2. It follows that

P[Lij ≥ t] ¤ 2’(t’1) .

Also note that L ≥ t implies that Lij ≥ t for some i, j, and hence

r r

P[Lij ≥ t] ¤ r2 2’t .

P[L ≥ t] ¤

i=1 j=i+1

472 Algorithms for ¬nite ¬elds

So we have

P[L ≥ t]

E[L] =

t≥1

P[L ≥ t] + P[L ≥ t]

=

t¤2 log2 r t>2 log2 r

r2 2’t

¤ 2 log2 r +

t>2 log2 r

2’t

¤ 2 log2 r +

t≥0

= 2 log2 r + 2.

That proves the claim.

As discussed in the paragraph above this theorem, the cost of each it-

eration of the main loop is O(k 2 len(q)) operations in F . Combining this

with the fact that E[L] = O(len(r)), it follows that the expected number

of operations in F for the entire algorithm is O(len(r)k 2 len(q)). This is

signi¬cantly better than the above quick-and-dirty estimate, but is not quite

the result we are after ”we have to get rid of the factor len(r). There are a

number of ways to do this. We sketch one such way, which is a bit ad hoc,

but su¬cient for our purposes.

Let us de¬ne

r r

S := Lij .

i=1 j=i+1

We claim that the total work performed by the algorithm in attempting to

split non-irreducible factors of g is

O(Sk 3 len(q)).

To see why this is so, consider one iteration of the inner loop of the algorithm,

where we are trying to split a factor h of g, where h is the product of

two or more irreducible factors of g. Let us write h = gi1 · · · gin , where

2 ¤ n ¤ r. On the one hand, the number of operations in F performed

in this step is at most ck deg(h)2 len(q) for some constant c, which we may

write as cn2 · k 3 len(q). On the other hand, each pair of indices (ij , ij ), with

1 ¤ j < j ¤ n, contributes 1 to the sum de¬ning S, for a total contribution

from pairs at this step of n(n ’ 1)/2 ≥ n2 /4. The claim now follows.

Algorithm EDF is a little silly in that it wastes time trying to split irre-

ducible factors (and although it would be trivial to modify the algorithm to

avoid this, the asymptotic running time would not be a¬ected signi¬cantly).

21.3 Factoring polynomials: the Cantor“Zassenhaus algorithm 473

It is easy to see that attempting to split a single irreducible factor takes

O(k 3 len(q)) operations in F , and hence the total amount of work wasted in

this way is O(Lrk 3 len(q)).

We next claim that E[Lij ] = O(1), for all i, j. Indeed,

2’(t’1) = 2.

P[Lij ≥ t] ¤

E[Lij ] =

t≥1 t≥1

It follows that

E[Lij ] = O(r2 ).

E[S] =

ij

Therefore, the expected number of operations in F performed by the algo-

rithm is at most a constant times

E[S]k 3 len(q) + E[L]rk 3 len(q) = O(r2 k 3 len(q) + r len(r)k 3 len(q)),

2

2 len(q)).

which is O(k

That completes the discussion of Algorithm EDF in the case p = 2.

The case p > 2

Now assume that p > 2, so that p, and hence also q, is odd. Algorithm EDF

in this case is exactly the same as above, except that in this case, we de¬ne

the polynomial Mk as

k ’1)/2

Mk := X(q ’ 1 ∈ F [X]. (21.3)

Just as before, for ± ∈ E with ± = θ(±1 , . . . , ±r ), we have

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

—

Note that each group Ei is a cyclic group of order q k ’ 1, and therefore, the

—

image of the (q k ’ 1)/2-power map on Ei is {±1}.

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

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

Ei . It follows that the values Mk (±i ) will be independently distributed. If

±i = 0, which happens with probability 1/q k , then Mk (±i ) = ’1; otherwise,

(q k ’1)/2

is uniformly distributed over {±1}, and so Mk (±i ) is uniformly

±i

distributed over {0, ’2}. That is to say,

0 with probability (q k ’ 1)/2q k ,

±

’1 with probability 1/q k ,

Mk (±i ) =

’2 with probability (q k ’ 1)/2q k .

Thus, if a := rep(Mk (±)), then gcd(a, g) will be the product of those factors

474 Algorithms for ¬nite ¬elds

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 zero or all non-zero. Assume r ≥ 2. Consider

the worst case, namely, when r = 2. In this case, a simple calculation shows

that the probability that we fail to split these two factors is

2 2

qk ’ 1 qk + 1 1

= (1 + 1/q 2k ).

+

2q k 2q k 2

The (very) worst case is when q k = 3, in which case the probability of failure

is at most 5/9.

The same quick-and-dirty analysis given just above Theorem 21.4 applies

here as well, but just as before, we can do better:

Theorem 21.5. In the case p > 2, Algorithm EDF uses an expected number

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

Proof. The analysis is essentially the same as in the case p = 2, except that

now the probability that we fail to split a given pair of irreducible factors

is at most 5/9, rather than equal to 1/2. The details are left as an exercise

for the reader. 2

21.3.3 Analysis of the whole algorithm

Given an arbitrary polynomial f ∈ F [X] of degree > 0, the distinct degree

factorization step takes O( 3 len(q)) operations in F . This step produces

a number of polynomials that must be further subjected to equal degree

factorization. If there are s such polynomials, where the ith polynomial has

degree i , for i = 1, . . . , s, then s

i=1 i = . Now, the equal degree factor-

ization step for the ith polynomial takes an expected number of O( 3 len(q))

i

operations in F (actually, our initial, “quick and dirty” estimate is good

enough here), and so it follows that the total expected cost of all the equal

degree factorization steps is O( i 3 len(q)), which is O( 3 len(q)), opera-

i