Factor modulo a small prime, lift, then recombine — the last step is the hard one
A factorisation modulo p lifts to a factorisation modulo any power of p, provided the factors are coprime modulo p. Lifting far enough that the coefficients exceed Mignotte's bound means the true integer factors can be read off — if the correct grouping of modular factors is known. Finding that grouping is the recombination problem, and its naive solution is exponential. The Lenstra–Lenstra–Lovász paper solved it, which is why LLL exists at all.
Learning objectives
- State Hensel's lemma and its coprimality hypothesis.
- Implement quadratic lifting and state its cost.
- Use Mignotte's bound to determine the required lifting height.
- Explain why recombination is the bottleneck.
- Outline the LLL and van Hoeij approaches to recombination.
Section 01Hensel's lemma
Suppose f ≡ gh (mod p) with g, h coprime modulo p. Then the factorisation lifts uniquely to modulo pk for every k.
- Compute s, t with sg + th ≡ 1 (mod p) by the extended Euclidean algorithm in Fp[x]. Coprimality is exactly what makes this possible.
- Given g, h correct modulo pk, set e ← f − gh, which is divisible by pk.
- Solve for corrections: δg ← te mod g and δh ← se mod h, both reduced modulo pk.
- Set g ← g + δg and h ← h + δh; the factorisation is now correct modulo p2k. The exponent doubles each round.
- Update s and t to the new modulus and repeat until pk exceeds the target.
If the modular factors share a root, the lift is not unique and the algorithm fails. This is why f must be squarefree and why p must not divide the discriminant — and why the choice of p includes a check that the factorisation modulo p is squarefree.
Section 02How far to lift: Mignotte's bound
The coefficients of any divisor of f over ℤ are bounded in terms of the degree and the norm of f:
Lifting until pk exceeds twice this bound guarantees that each true factor is determined by its residue modulo pk, taken in the symmetric range.
Mignotte's bound is worst-case and usually far above the actual coefficient sizes, so the lifting height — and therefore the cost of every subsequent operation — is larger than strictly necessary. Practical implementations lift incrementally, attempt recombination early, and lift further only if it fails.
Section 03The recombination problem
Suppose f factors into r irreducible factors modulo pk. Each true factor over ℤ is a product of some subset of them. Testing all subsets costs 2r trial divisions.
The hard case is a polynomial that is irreducible over ℤ but splits into many factors modulo every prime — the Swinnerton-Dyer polynomials are the standard family. Every subset must be rejected, so the naive search runs its full exponential course before concluding that no factorisation exists.
| Strategy | Cost | Notes |
|---|---|---|
| Exhaustive subsets (Zassenhaus) | O(2r) | Fast when r is small, which is the common case in practice |
| LLL on a coefficient lattice | Polynomial | The original polynomial-time result; the lattice dimension makes it slow in practice |
| van Hoeij's knapsack method | Polynomial, and fast | Reduces a much smaller lattice built from power sums — the current standard |
| Multiple primes | Heuristic | Factor modulo several primes; the true degrees must be consistent across all of them |
Section 04The complete pipeline
- Stage 01PreprocessRemove content, make primitive, take the squarefree part. Handle degree 0 and 1 directly.
- Stage 02Choose a primeSelect p not dividing the leading coefficient or the discriminant, so that f stays squarefree modulo p. Try several and keep the one giving the fewest factors.
- Stage 03Factor modulo pApply the finite-field pipeline: squarefree, distinct-degree, equal-degree.
- Stage 04Hensel liftLift to pk beyond Mignotte's bound, using quadratic lifting.
- Stage 05RecombineFind the subsets of modular factors forming true integer factors; verify each by exact division.
The number of modular factors varies substantially with p, and recombination cost depends on it directly. Trying several candidate primes and keeping the one with the fewest factors is cheap and frequently pays for itself several times over.
ReferenceFrequently asked questions
Why lift quadratically rather than linearly?
Because the number of rounds drops from O(k) to O(log k). Each quadratic round is more expensive, but the reduction in round count dominates once the target height is more than a few powers of p.
Does this extend to multivariate polynomials?
Yes — lift with respect to one variable, treating the others as parameters, using the ideal generated by (y − a) in place of p. The recombination problem reappears in the same form, and the same techniques apply.
Is factoring over a number field similar?
Structurally yes: reduce modulo a prime ideal of good reduction, factor over the residue field, lift and recombine. The extra difficulty is choosing a prime ideal of degree 1 that does not divide the relevant discriminants, and handling the denominators introduced by the integral basis.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.