MPQS

MPQS, or Multiple Polynomial Quadratic Sieve, is an integer factorization algorithm that extends the Quadratic Sieve by using several polynomials to generate candidate relations in parallel. It was the dominant practical method for factoring medium-sized integers before the General Number Field Sieve (GNFS) became the preferred approach for very large numbers.

The method works by building a factor base of small primes and selecting a set of quadratic polynomials f_i(x) that depend on the target number N. As x runs over a range, the values f_i(x) are tested for smoothness with respect to the factor base. Each smooth value yields a relation, recording the exponents of the prime factors modulo 2. Once a sufficient number of independent relations have been gathered, they are combined by solving a linear system modulo 2 to obtain a nontrivial dependency, which corresponds to a congruence of squares modulo N. From this congruence, the greatest common divisor of N with the difference of the two squares provides a nontrivial factor of N, assuming the dependency is nondegenerate.

MPQS saw its peak in practical use during the 1990s and early 2000s for numbers up to roughly a hundred digits, offering improvements over a single quadratic polynomial by increasing the density of usable relations. The development of GNFS eventually surpassed MPQS for very large integers, leading to MPQS being largely superseded in modern factoring practice. Nonetheless, MPQS remains an important milestone in the history of computational number theory and influenced subsequent factoring techniques.

See also: Quadratic Sieve, General Number Field Sieve, integer factorization.