Polynomial Factorisation
Factoring Polynomials over the Integers
The modular-lift-recombine pipeline, the exponential recombination problem, and the LLL-based algorithm that makes factorisation polynomial time.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0569
Factoring a polynomial over the integers reduces to the finite field case plus lifting, but the reduction leaves a combinatorial problem behind. Removing that problem is the celebrated application of lattice reduction.
The classical pipeline
Zassenhaus factorisation
- PreprocessRemove content and repeated factors.
- Choose a primeNot dividing the leading coefficient or the discriminant.
- Factor modulo pUsing the finite field pipeline.
- LiftBy Hensel lifting past the Mignotte bound.
- RecombineDetermine which products of modular factors are true integer factors.
The recombination problem
The classical algorithm is therefore exponential in the worst case despite every individual stage being polynomial. In practice it is usually fast, because random polynomials do not behave this way.
The LLL-based algorithm
Instead of searching combinations, construct a lattice in which a true factor corresponds to a short vector, then apply LLL.
| Algorithm | Worst case | Typical case |
|---|---|---|
| Zassenhaus | Exponential in the modular factor count | Fast; usually few factors to recombine |
| LLL-based | Polynomial | Slower constant factor |
| Hybrid | Polynomial | Fast — try recombination briefly, fall back to LLL |
Why this result mattered
Choosing the prime well
Trying several primes and keeping the one with the fewest modular factors materially reduces recombination work. Since the number of modular factors varies considerably between primes, this cheap heuristic is always worth applying.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.5.2-3.5.4. 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.