Quadratic Sieve Factorization Method

A procedure used in conjunction with Dixon's Factorization Method to factor large numbers. The $r$s are chosen as

$$\left\lfloor{\sqrt{n}}\right\rfloor +k,$$ (1)

where $k=1$, 2, ... and $\left\lfloor{x}\right\rfloor$ is the Floor Function. We are then looking for factors $p$ such that

$$n\equiv r^2\ \left({{\rm mod\ } {p}}\right),$$ (2)

which means that only numbers with Legendre Symbol $(n/p)=1$ (less than $N=\pi(d)$ for trial divisor $d$) need be considered. The set of Primes for which this is true is known as the Factor Base. Next, the Congruences

$$x^2\equiv n\ \left({{\rm mod\ } {p}}\right)$$ (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 $\mathop{\rm exp}\nolimits (\sqrt{\log n\log\log n}\,)$ 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.

See also Prime Factorization Algorithms, 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). World Scientific, pp. 163-174, 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. ftp://nimbus.anu.edu.au/pub/Brent/rpb115.dvi.Z.

Bressoud, D. M. Ch. 8 in Factorization and Prime 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. ``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.