# Factoring polynomials over finite fields

The problem considered in this section is the following: given a polynomial *f(x)* e F, [ж], wither = p^{m}, find its factorization/(ж) = *fi{x) ^{ei} f_{2}(x)^{e2} • ■ ■ ft(x)^{e}‘*, where each /,(ж) is an irreducible polynomial in F,,[;r] and each e* > 1. (e, is called the

*multiplicity’*of the factor /, (ж).) Several situations call for the factoring of polynomials over finite fields, such as index-calculus algorithms in F^.,, (Example 3.70) and Chor-Rivest public-key encryption (§8.6.2). This section presents an algorithm for square-free factorization, and Berlekamp's classical deterministic algorithm for factoring polynomials which is efficient if the underlying field is small. Efficient randomized algorithms are known for the case of large

*q*references are provided on page 132.

## Square-free factorization

Observe first that *f(x)* may be divided by its leading coefficient. Thus, it may be assumed that *f(x)* is monic (see Definition 2.187). This section shows how the problem of factoring a monic polynomial *f(x)* may then be reduced to the problem of factoring one or more monic square-free polynomials.

3.109 Definition Let *f(x)* e FJx], Then *f(x)* is *square-free* if it has no repeated factors, i.e., there is no polynomial *g(x)* with deg *g(x) >* 1 such that *g(x) ^{2}* divides

*f(x).*The

*square- free factorization*of

*f(x)*is

*f(x)*= ntr

*f>(*> where each

^{x}Y*f*is a square-free polynomial and gcd(/;(x),

_{t}(x)*fj(x))*= 1 for

*i ф j.*(Some of the

*f,(x)*in the square-free factorization of

*f(x)*may be 1.)

Let *f(x) =* £”_{=0} *a, x’* be a polynomial of degree *n >* 1. The (formal) *derivative* of *f(x)* is the polynomial *f'(x)* = ^ "j",,^{[1]} a_{i+1} *(i* + l)x*. If *f'(x)* = 0, then, because *p* is the characteristic of F_{g}, in each term *щх ^{г}* of

*f(x)*for which

*а, Ф*0, the exponent of

*x*must

be a multiple *oip.* Hence, *f(x)* has the form *f(x) = a(x) ^{p},* where

*a(x) = YZ'i=o n‘p*and the problem of finding the square-free factorization of

^{P}x^{[1]},*f(x)*is reduced to finding that of a(x). Now, it is possible that

*a'(x) =*0, but repeating this process as necessary, it may be assumed that

*f'(x) ф*0.

Next, let *g(x) =* gcd *(f(x), f'{x)).* Noting that an irreducible factor of multiplicity *k *in *f(x)* will have multiplicity *к —* 1 in *f'(x*) if gcd *(k,p) =* 1, and will retain multiplicity *к* in *f'(x*) otherwise, the following conclusions may be drawn. If *g(x) =* 1, then *f(x) *has no repeated factors; and if *g(x)* has positive degree, then *g(x)* is a non-trivial factor of *f{x),* and *f(x)/g(x)* has no repeated factors. Note, however, the possibility of *g(x) *havmg repeated factors, and, indeed, the possibility that *g'(x) =* 0. Nonetheless, *g(x)* can be refined further as above. The steps are summarized in Algorithm 3.110. In the algorithm, *F* denotes the square-free factorization of a factor of *f(x)* in factored form.

3.110 Algorithm Square-free factorization SQUARE-FREE(/(a:))

INPUT: a monic polynomial *f(x*) e FJx] of degree > 1, where F,_{;} has characteristic *p. *OUTPUT: the square-free factorization of *f{x).*

- 1. Set i-t-1, F-t-1, and compute
*f(x).* - 2. If
*f'(x) =*0 then set*f(x*)^-*f(x)Fr*and F^(SQUARE-FREE(/(x)))p.

Otherwise (i.e. *f'(x) ф* 0) do the following:

- 2.1 Compute gcd(/(x),
*f'{x))*and*h(x)* - 2.2 While
*h(x) ф*1 do the following:

Compute *h(x)<—* gcd(/i(x), *g{x))* and *l(x)<—h(x)/h(x).*

Set *F ■ l(x) ^{1}, it— i* + 1,

*h(x)* and

*g(x)<—g(x)/h(x).*

*
*

- 2.3 If
*g(x) ф*1 then set*g{x)^g{x)*and^{1}/P*F^F ■*(SQUARE-FREE(_{5}(x)))p. - 3. Return(F).

- [1] Once the square-free factorization f(x) = f, (х)г is found, the square-free polynomials fi(x), /г(х),... , fk(x) need to be factored in order to obtain the complete factorization of f{x).
- [2] Once the square-free factorization f(x) = f, (х)г is found, the square-free polynomials fi(x), /г(х),... , fk(x) need to be factored in order to obtain the complete factorization of f{x).