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.
. Pick values of 
given by
,
2, ... and 
is the floor function. We are then looking for
factors 
such that
(less than 
for trial divisor 
, where 
is the prime counting
function) need be considered. The set of primes
for which this is true is known as the factor base.
Next, the congruences
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.
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.
. 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.
