f = f1 · · · fr ,

and let

θ : E1 — · · · — Er ’ E

be the F -algebra isomorphism from the Chinese remainder theorem, where

Ei := F [X]/(fi ) is an extension ¬eld of F of ¬nite degree for i = 1, . . . , r.

q

Now, for ± = θ(±1 , . . . , ±r ) ∈ E, we have ±q = ± if and only if ±i = ±i for

i = 1, . . . , r; moreover, by Theorem 20.8, we know that for any ±i ∈ Ei , we

q

have ±i = ±i if and only if ±i ∈ F . Thus, we may characterize B as follows:

B = {θ(c1 , . . . , cr ) : c1 , . . . , cr ∈ F }.

Since B is a subalgebra of E, then as F -vector spaces, B is a subspace of

E. Of course, E has dimension over F , with the natural basis 1, ·, . . . , · ’1 ,

where · := [X]f . As for the Berlekamp subalgebra, from the above charac-

terization of B, it is evident that

θ(1, 0, . . . , 0), θ(0, 1, 0, . . . , 0), . . . , θ(0, . . . , 0, 1)

is a basis for B over F , and hence, B has dimension r over F .

Now we come to the actual factoring algorithm.

Stage 1: Construct a basis for B

The ¬rst stage of Berlekamp™s factoring algorithm constructs a basis for B

over F . We can easily do this using Gaussian elimination, as follows. Let

ρ : E ’ E be the map that sends ± ∈ E to ±q ’ ±. Since the qth power map

on E is an F -algebra homomorphism (see Theorem 20.7)”and in particular,

an F -linear map ” the map ρ is also F -linear. Moreover, the kernel of ρ is

21.4 Factoring polynomials: Berlekamp™s algorithm 479

none other than the Berlekamp subalgebra B. So to ¬nd a basis for B, we

simply need to ¬nd a basis for the kernel of ρ using Gaussian elimination

over F , as in §15.4.

To perform the Gaussian elimination, we need to choose an ordered basis

for E over F , and construct a matrix Q ∈ F — that represents ρ with

respect to that ordered basis as in §15.2, so that evaluation of ρ corresponds

to multiplying a row vector on the right by Q. We are free to choose

an ordered basis in any convenient way, and the most convenient ordered

basis, of course, is (1, ·, . . . , · ’1 ), as this directly corresponds to the way

we represent elements of E for computational purposes. Let us de¬ne the

F -vector space isomorphism

F 1— ’ E

:

(21.6)

’1

’1 ) ’ a0 + a1 · + · · · + a

(a0 , . . . , a ’1 · .

The maps and ’1 are best thought of as “type conversion operators”

that require no actual computation to evaluate. The matrix Q, then, is the

— matrix whose ith row, for i = 1, . . . , , is ’1 (ρ(· i’1 )). Note that if

± := · q , then ρ(· i’1 ) = (· i’1 )q ’ · i’1 = (· q )i’1 ’ · i’1 = ±i’1 ’ · i’1 . This

observation allows us to construct the rows of Q by ¬rst computing ± as · q

via repeated squaring, and then just computing successive powers of ±.

After we construct the matrix Q, we apply Gaussian elimination to get

row vectors v1 , . . . , vr that form a basis for the row null space of Q. It is at

this point that our algorithm actually discovers the number r of irreducible

factors of f . We can then set βi := (vi ) for i = 1, . . . , r to get our basis for B.

Putting this altogether, we have the following algorithm to compute a

basis for the Berlekamp subalgebra. It takes as input a monic square-free

polynomial f of degree > 0. With E := F [X]/(f ), · := [X]f ∈ E, and as

de¬ned in (21.6), the algorithm runs as follows:

Algorithm B1:

let Q be an — matrix over F (initially with unde¬ned entries)

compute ± ← · q using repeated squaring

β ← 1E

for i ← 1 to do // invariant: β = ±i’1 = (· i’1 )q

Q(i) ← ’1 (β), Q(i, i) ← Q(i, i) ’ 1, β ← β±

compute a basis v1 , . . . , vr of the row null space of Q using

Gaussian elimination

for i = 1, . . . , r do βi ← (vi )

output β1 , . . . , βr

480 Algorithms for ¬nite ¬elds

The correctness of Algorithm B1 is clear from the above discussion. As

for the running time:

3 2 len(q))

Theorem 21.9. Algorithm B1 uses O( + operations in F .

Proof. This is just a matter of counting. The computation of ± takes

O(len(q)) operations in E using repeated squaring, and hence O( 2 len(q))

operations in F . To build the matrix Q, we have to perform an additional

O( ) operations in E to compute the successive powers of ±, which trans-

lates into O( 3 ) operations in F . Finally, the cost of Gaussian elimination

is an additional O( 3 ) operations in F . 2

Stage 2: Splitting with B

The second stage of Berlekamp™s factoring algorithm is a probabilistic proce-

dure that factors f using a basis β1 , . . . , βr for B. As we did with Algorithm

EDF in §21.3.2, we begin by discussing how to e¬ciently split f into two

non-trivial factors, and then we present a somewhat more elaborate algo-

rithm that completely factors f .

Let M1 ∈ F [X] be the polynomial de¬ned by (21.2) and (21.3); that is,

w’1 2j

if p = 2,

j=0 X

M1 :=

X(q’1)/2 ’ 1 if p > 2.

Using our basis for B, we can easily generate a random element β of B

by simply choosing c1 , . . . , cr at random, and computing β := i ci βi . If

β = θ(b1 , . . . , br ), then the bi will be uniformly and independently distributed

over F . Just as in Algorithm EDF, gcd(rep(M1 (β)), f ) will be a non-trivial

factor of f with probability at least 1/2, if p = 2, and probability at least

4/9, if p > 2.

That is the basic splitting strategy. We turn this into an algorithm to

completely factor f using the same technique of iterative re¬nement that

was used in Algorithm EDF. That is, at any stage of the algorithm, we have

a partial factorization f = h∈H h, which we try to re¬ne by attempting

to split each h ∈ H using the strategy outlined above. One technical dif-

¬culty is that to split such a polynomial h, we need to e¬ciently generate

a random element of the Berlekamp subalgebra of F [X]/(h). A particularly

e¬cient way to do this is to use our basis for the Berlekamp subalgebra

of F [X]/(f ) to generate a random element of the Berlekamp subalgebra of

F [X]/(h) for all h ∈ H simultaneously. Let gi := rep(βi ) for i = 1, . . . , r.

If we choose c1 , . . . , cr ∈ F at random, and set g := c1 g1 + · · · + cr gr , then

[g]f is a random element of the Berlekamp subalgebra of F [X]/(f ), and by

21.4 Factoring polynomials: Berlekamp™s algorithm 481

the Chinese remainder theorem, it follows that the values [g]h for h ∈ H

are independently distributed, with each [g]h uniformly distributed over the

Berlekamp subalgebra of F [X]/(h).

Here is the algorithm for completely factoring a polynomial, given a basis

for the corresponding Berlekamp subalgebra. It takes as input a monic,

square-free polynomial f of degree > 0, together with a basis β1 , . . . , βr for

the Berlekamp subalgebra of F [X]/(f ). With gi := rep(βi ) for i = 1, . . . , r,

the algorithm runs as follows:

Algorithm B2:

H ← {f }

while |H| < r do

choose c1 , . . . , cr ∈ F at random

g ← c1 g1 + · · · + cr gr ∈ F [X]

H ←…

for each h ∈ H do

β ← [g]h ∈ F [X]/(h)

d ← gcd(rep(M1 (β)), 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. As for its expected running

time, we can get a quick-and-dirty upper bound as follows:

• The cost of generating g in each loop iteration is O(r ) operations

in F . For a given h, the cost of computing β := [g]h ∈ F [X]/(h)

is O( deg(h)) operations in F , and the cost of computing M1 (β) is

O(deg(h)2 len(q)) operations in F . Therefore, the number of opera-

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

constant times

deg(h)2

r+ deg(h) + len(q)

h∈H h∈H

2