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.
A type of quadratic sieve can also be used to generate the prime numbers by considering the parabola . Consider the points lying on the parabola with integer
coordinates
for ,
3, .... Now connect pairs of integer points lying on the two branches of the parabola,
above and below the -axis.
Then the points where these lines intersect the
-axis correspond to composite numbers,
while those integer points on the positive -axis which are not crossed by any lines are prime numbers.
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). Singapore: World Scientific, pp. 163-174, 1995.Boender,
H. and te Riele, H. J. J. "Factoring Integers with Large Prime Variations
of the Quadratic Sieve." Preprint. Centrum voor Wiskunde en Informatica, No. NM-R9513,
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.Bressoud, D. M. Ch. 8 in Factorization
and Primality 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. "The
Quadratic Sieve Factoring Algorithm." In Advances
in Cryptology: Proceedings of EUROCRYPT 84 (Ed. T. Beth, N. Cot,
and I. Ingemarsson). New York:Springer-Verlag, pp. 169-182, 1985.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.Silverman, R. D.
"The Multiple Polynomial Quadratic Sieve." Math. Comput.48,
329-339, 1987.