Number Field Sieve Factorization Method

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

$${\mathcal O}\{\mathop{\rm exp}\nolimits [c(\log n)^{1/3} (\log\log n)^{2/3}]\},$$

reducing the exponent over the Continued Fraction Factorization Algorithm and Quadratic Sieve Factorization Method. There are three values of $c$ relevant to different flavors of the method (Pomerance 1996). For the ``special'' case of the algorithm applied to numbers near a large Power,

$$c=({\textstyle{32\over 9}})^{1/3} = 1.526285\ldots,$$

for the ``general'' case applicable to any Odd Positive number which is not a Power,

$$c=({\textstyle{64\over 9}})^{1/3} = 1.922999\ldots,$$

and for a version using many Polynomials (Coppersmith 1993),

$$c={\textstyle{1\over 3}}(92+26\sqrt{13}\,)^{1/3} = 1.901883\ldots.$$

References

Coppersmith, D. ``Modifications to the Number Field Sieve.'' J. Cryptology 6, 169-180, 1993.

Coppersmith, D.; Odlyzko, A. M.; and Schroeppel, R. ``Discrete Logarithms in GF($p$).'' Algorithmics 1, 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, M. ``A Multiple Polynomial General Number Field Sieve.'' Algorithmic Number Theory (Talence, 1996). New York: Springer-Verlag, pp. 99-114, 1996.

Elkenbracht-Huizing, 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.

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.

Pomerance, C. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.