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

(1) |

(2) |

(3) |

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.

© 1996-9

1999-05-25