![[a_polynomialfactorization graphic]](images/a_polynomialfactorization.gif){kind=small}
Polynomial Factorization
![[polynomial_factorization graphic]](images/polynomial_factorization.gif)
The "Berlekamp algorithm" known to teachers of introductory algebra courses provides a quick and elegant way to factor polynomials over a small finite field of order q. The monic polynomial to be factored is f(x), of degree n. Its coefficients are known. The key idea is to find and exploit solutions, g(x), of the congruence
Because q is the order of the finite field, it is not hard to show that the coefficients of g satisfy a system of n linear equations,
Here Q and I are n by n q-ary matrices (matrices over Fq). The entries of Q can be readily computed from the polynomial f(x).
One then finds solution vectors, g, and corresponding polynomials, g. It is well-known that
(g(x)
-
β),
where β runs over all q elements in the field. Since we now have a factorization of a multiple of f(x), we can factor f(x) by computing its gcd with each factor of the multiple.
This algorithm also provides a strong attack on factoring polynomials over the integers. Begin by factoring over Zn, for some quite large integer n. Berlekamp [1972] factored modulo a large prime; Zassenhaus factored modulo pm, where p is a small prime and m is moderately large. Both methods are very fast for most polynomials, but there are rare polynomials which have many factors of small degrees modulo every prime-power, yet have few if any proper factors over Z. Lenstra later devised a method that handles these bad cases nicely.
Algebraic Coding Theory, McGraw-Hill, 1968; revised edition, Aegean Park Press, Laguna Hills, CA, 1984. See Chapter 6.
"Factoring Polynomials over Large Finite Fields", Mathematics of Computation 24:713-735 (1972); Math. Rev. 48:1943.