Polynomial Factorisation
Polynomial Factorisation: Overall Strategy
The three-stage pipeline used to factor polynomials over finite fields and the integers, and why the stages are ordered as they are.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0562
Polynomial factorisation is not one algorithm but a pipeline. Each stage reduces the problem to a strictly easier one, and the ordering is forced by what each stage assumes about its input.
The pipeline over a finite field
Factoring over a finite field
- Squarefree factorisationSeparate repeated factors, producing polynomials with no repeated roots. Deterministic and cheap, using GCD with the derivative. See squarefree factorisation.
- Distinct degree factorisationSeparate the irreducible factors by their degree, using GCDs against Frobenius powers. Deterministic. See distinct degree factorisation.
- Equal degree splittingSeparate factors of the same degree. Probabilistic. See Cantor-Zassenhaus.
Why the ordering is forced
| Stage | Assumes about its input |
|---|---|
| Squarefree factorisation | Nothing |
| Distinct degree | Input is squarefree |
| Equal degree splitting | Input is squarefree and all factors have known equal degree |
The alternative: Berlekamp
Berlekamp's algorithm takes a different route entirely, using linear algebra over the field rather than GCD computations. It is deterministic for small fields and is still the method of choice when the field is small and the degree modest.
Over the integers
Factoring over the integers reduces to the finite field case: factor modulo a well-chosen prime, lift the factorisation to a prime power with Hensel lifting, then determine which combinations of modular factors correspond to true integer factors.
Choosing the prime
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.4.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.