## 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

reducing the exponent over the Continued Fraction Factorization Algorithm and Quadratic Sieve Factorization Method. 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,

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

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

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().'' 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 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.