An extremely fast factorization method developed by Pollard which was used to factor the RSA-130 number. This method is the most powerful
known for factoring general numbers, and has complexity
(1)
reducing the exponent over the continued fraction factorization algorithm and quadratic
sieve. There are three values of relevant to different flavors of the method (Pomerance 1996).
For the "special" case of the algorithm applied to numbers near a large
power,
(2)
for the "general" case applicable to any oddpositive number which is not a power,
(3)
and for a version using many polynomials (Coppersmith
1993),
Coppersmith, D. "Modifications to the Number Field Sieve." J. Cryptology6, 169-180, 1993.Coppersmith,
D.; Odlyzko, A. M.; and Schroeppel, R. "Discrete Logarithms in GF()." Algorithmics1,
1-15, 1986.Cowie, J.; Dodson, B.; Elkenbracht-Huizing, R. M.; Lenstra,
A. K.; Montgomery, P. L.; Zayer, J. A. "World Wide Number Field
Sieve Factoring Record: On to 512 Bits." In Advances
in Cryptology--ASIACRYPT '96 (Kyongju) (Ed. K. Kim and T. Matsumoto.)
New York: Springer-Verlag, pp. 382-394, 1996.Elkenbracht-Huizing,
R.-M. "A Multiple Polynomial General Number Field Sieve." Algorithmic
Number Theory (Talence, 1996). New York: Springer-Verlag, pp. 99-114, 1996.Elkenbracht-Huizing,
R.-M. "An Implementation of the Number Field Sieve." Experiment. Math.5,
231-253, 1996.Elkenbracht-Huizing, R.-M. "Historical Background
of the Number Field Sieve Factoring Method." Nieuw Arch. Wisk.14,
375-389, 1996.Elkenbracht-Huizing, R.-M. Factoring Integers with
the Number Field Sieve. Doctor's Thesis, Leiden University, 1997.Lenstra,
A. K. and Lenstra, H. W. Jr. "Algorithms in Number Theory." In
Handbook
of Theoretical Computer Science, Volume A: Algorithms and Complexity (Ed.
J. van Leeuwen). New York: Elsevier, pp. 673-715, 1990.Lenstra,
A. K. and Lenstra, H. W. Jr. The
Development of the Number Field Sieve. Berlin: Springer-Verlag, 1993.Pomerance,
C. "A Tale of Two Sieves." Not. Amer. Math. Soc.43, 1473-1485,
1996.