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.

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.