 Factoring polynomials over finite fields

The problem considered in this section is the following: given a polynomial f(x) e F, [ж], wither = pm, find its factorization/(ж) = fi{x)ei f2(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>(xY> where each ft(x) is a square-free polynomial and gcd(/;(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",, ai+1 (i + l)x*. If f'(x) = 0, then, because p is the characteristic of Fg, 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‘pPx, and the problem of finding the square-free factorization of 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)1/P and F^F ■ (SQUARE-FREE(5(x)))p.
• 3. Return(F).

•  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).
•  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).