mathworld.wolfram.com

Quadratic Sieve -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Wed Sep 20 2000
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

A sieving procedure that can be used in conjunction with Dixon's factorization method to factor large numbers n. Pick values of r given by

r=|_sqrt(n)_|+k,

(1)

where k=1, 2, ... and |_x_| is the floor function. We are then looking for factors p such that

n=r^2 (mod p),

(2)

which means that only numbers with Legendre symbol (n/p)=1 (less than N=pi(d) for trial divisor d, where pi(d) 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

x^2=n (mod p)

(3)

must be solved for each p in the factor base. Finally, a sieve is applied to find values of f(r)=r^2-n 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 f(r)s, yielding a perfect square.

The method requires about exp(sqrt(lnnlnlnn)) 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.

QuadraticSieve

A type of quadratic sieve can also be used to generate the prime numbers by considering the parabola x=y^2. Consider the points lying on the parabola with integer coordinates (y^2,y) for y=2, 3, .... Now connect pairs of integer points lying on the two branches of the parabola, above and below the x-axis. Then the points where these lines intersect the x-axis correspond to composite numbers, while those integer points on the positive x-axis which are not crossed by any lines are prime numbers.

See also

Number Field Sieve, Prime Factorization Algorithms, Quadratic, Smooth Number

Explore with Wolfram|Alpha

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

Subject classifications