A procedure used in conjunction with Dixon's Factorization Method to factor large numbers. The s are chosen as

 (1)

where , 2, ... and is the Floor Function. We are then looking for factors such that
 (2)

which means that only numbers with Legendre Symbol (less than for trial divisor ) need be considered. The set of Primes for which this is true is known as the Factor Base. Next, the Congruences
 (3)

must be solved for each in the Factor Base. Finally, a sieve is applied to find values of which can be factored completely using only the Factor Base. Gaussian Elimination is then used as in Dixon's Factorization Method in order to find a product of the s, yielding a Perfect Square.

The method requires about steps, improving on the Continued Fraction Factorization Algorithm by removing the 2 under the Square Root (Pomerance 1996). The use of multiple Polynomials gives a better chance of factorization, requires a shorter sieve interval, and is well-suited to parallel processing.

References

Alford, W. R. and Pomerance, C. Implementing the Self Initializing Quadratic Sieve on a Distributed Network.'' In Number Theoretic and Algebraic Methods in Computer Science, Proc. Internat. Moscow Conf., June-July 1993 (Ed. A. J. van der Poorten, I. Shparlinksi, and H. G. Zimer). World Scientific, pp. 163-174, 1995.

Brent, R. P. Parallel Algorithms for Integer Factorisation.'' In Number Theory and Cryptography (Ed. J. H. Loxton). New York: Cambridge University Press, 26-37, 1990. ftp://nimbus.anu.edu.au/pub/Brent/rpb115.dvi.Z.

Bressoud, D. M. Ch. 8 in Factorization and Prime Testing. New York: Springer-Verlag, 1989.

Gerver, J. Factoring Large Numbers with a Quadratic Sieve.'' Math. Comput. 41, 287-294, 1983.

Lenstra, A. K. and Manasse, M. S. Factoring by Electronic Mail.'' In Advances in Cryptology--Eurocrypt '89 (Ed. J.-J. Quisquarter and J. Vandewalle). Berlin: Springer-Verlag, pp. 355-371, 1990.

Pomerance, C. A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.

Pomerance, C.; Smith, J. W.; and Tuler, R. A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Method.'' SIAM J. Comput. 17, 387-403, 1988.