Polynomial Factorisation
Hensel Lifting for Polynomial Factors
Lifting a factorisation modulo a prime to a factorisation modulo a prime power, the quadratic variant, and the coprimality condition.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0568
Hensel lifting converts a factorisation modulo a prime into one modulo an arbitrarily high power of that prime. It is the bridge between the easy finite field problem and the hard integer one.
The principle
Given a factorisation modulo p into coprime factors, there is a unique lift modulo p^2 agreeing with it, and the process iterates. The correction is computed from the Bezout coefficients of the factors.
Hensel lifting
- Factor modulo pUsing finite field methods.
- Compute Bezout coefficientsExpress one as a combination of the factors — see the extended algorithm.
- Compute the errorThe difference between f and the product of the current factors, divisible by the current modulus.
- CorrectDistribute the error between the factors using the Bezout coefficients.
- IterateRepeat to the required precision.
Linear versus quadratic lifting
| Variant | Precision growth | Per-step cost |
|---|---|---|
| Linear | One power per step | Cheap; Bezout coefficients reused |
| Quadratic | Doubles each step | More expensive; coefficients must also be lifted |
The coprimality condition
Multifactor lifting
With more than two factors, lift pairwise in a tree: split the factors into two groups, lift the two products, then recurse. This is more efficient than lifting each factor against the product of all others.
How far to lift
Far enough that the true integer coefficients are determined — that is, until the prime power exceeds twice the Mignotte bound. The factor of two accommodates signed representatives.
Other uses
- Lifting square roots modulo a prime to prime powers — see square roots.
- Lifting roots of polynomials, the p-adic Newton iteration.
- The Dedekind criterion in maximal order computation.
- Constructing p-adic approximations for Newton polygon methods.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.5.3. 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.