Modern Factoring Methods
The Multiple Polynomial Quadratic Sieve
MPQS: using many polynomials with short intervals to keep values small, and the self-initialising variant.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0674
The single-polynomial sieve suffers from values that grow as the interval extends. Using many polynomials, each sieved over a short interval, keeps every value small and is the decisive improvement.
The problem
The fix
Use a family of quadratic polynomials, each with a short interval around its own centre where values stay small. Switch polynomials rather than extending any one interval.
MPQS polynomial generation
- Choose the leading coefficientAs a product of factor base primes, sized so values remain small.
- Solve for the middle coefficientBy square roots modulo each prime factor, combined by the Chinese remainder theorem.
- Derive the constantFrom the discriminant condition.
- Compute sieve rootsFor each factor base prime under the new polynomial.
- Sieve the short intervalThen move to the next polynomial.
The initialisation cost
Self-initialisation
SIQS chooses the leading coefficient as a product of several primes, then generates many polynomials sharing it by varying signs in the Chinese remainder reconstruction. Sieve roots for the family are obtained by cheap updates rather than full recomputation.
| Variant | Value size | Initialisation cost |
|---|---|---|
| Single polynomial | Grows across a long interval | Once |
| MPQS | Small throughout | Per polynomial — significant |
| SIQS | Small throughout | Amortised across a family |
Choosing the interval length
Where the sieve stands
SIQS is the method of choice for targets up to roughly a hundred digits. Beyond that the number field sieve is faster — see the number field sieve and method comparison.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.4.2-10.4.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.