Polynomial Factorisation
Mignotte Bounds on Polynomial Factors
Bounding the coefficients of any factor of an integer polynomial, and why such a bound makes modular and lifting methods complete algorithms.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0567
Modular and Hensel-based factorisation both need to know when enough precision has been reached. The Mignotte bound answers that: it limits the size of coefficients of any factor in terms of the original polynomial.
The bound
Any factor of an integer polynomial has coefficients bounded in terms of the Euclidean norm of the original and the factor's degree.
Where it is used
| Method | Role of the bound |
|---|---|
| Hensel lifting | Determines the prime power to lift to |
| Modular polynomial GCD | Determines how many primes are needed |
| Integer factorisation | Sizes the lattice in the LLL construction |
| Verification | A candidate factor exceeding the bound is immediately rejected |
Looseness
A common engineering compromise is to lift to a smaller precision, attempt reconstruction, and verify by exact division. If verification fails, lift further. This is faster in the typical case and remains correct because the verification is exact.
Leading coefficients
Related bounds
Cauchy and related bounds limit the absolute values of the roots rather than the coefficients of factors. They are used in numerical root finding to bound the search region, and in Newton polygon analysis to bound valuations.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.5.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.