info prev up next book cdrom email home

Quadratic Sieve Factorization Method

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

\begin{displaymath}
\left\lfloor{\sqrt{n}}\right\rfloor +k,
\end{displaymath} (1)

where $k=1$, 2, ... and $\left\lfloor{x}\right\rfloor $ is the Floor Function. We are then looking for factors $p$ such that
\begin{displaymath}
n\equiv r^2\ \left({{\rm mod\ } {p}}\right),
\end{displaymath} (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
\begin{displaymath}
x^2\equiv n\ \left({{\rm mod\ } {p}}\right)
\end{displaymath} (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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25