Quadratic Sieve
A sieving procedure that can be used in conjunction with Dixon's factorization method to factor large numbers 
. Pick values of
given by
 |
(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 
, 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
 |
(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.
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.
SEE ALSO: Number Field Sieve,
Prime Factorization Algorithms,
Quadratic,
Smooth Number
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). 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.
Referenced on Wolfram|Alpha:
Quadratic Sieve
CITE THIS AS:
Weisstein, Eric W. "Quadratic Sieve."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/QuadraticSieve.html
Contact the MathWorld Team
prime factorization