What is the number field sieve?
The number field sieve (NFS) is the asymptotically fastest known algorithm for factoring large composite integers which have no known special form. It was introduced by J.M. Pollard in 1988 and later refined by various well-known members of the number theory community.

The number field sieve has been used for some of the most impressive factorizations to date. Some of the more famous efforts are the factorizations of RSA-130, RSA-140 and and the ground-breaking factorization of RSA-512.

The number field sieve has fundamental similarities to simpler and previously known algorithms. At its core, as with the continued fraction method and the quadratic sieve, is the goal to find a congruence of squares. If N, the number to be factored, is composed of two prime factors, each solution to x^2==y^2 mod N, has a 50% chance of producing a non-trivial factorization of N.

Whereas previous algorithms seek a congruence of squares through rather elementary means, the number field sieve uses the theory of algebraic number rings to find a congruence of squares in a more efficient way.

What is the difference between special and general number field sieve?
The number field sieve is particularly efficient for numbers of the form: N=r^e+s where r and s are small. Examples of such numbers are found in the Cunningham Project which seeks to factor the numbers b^n±1.

The Cunningham project has the distinction of being the most likely candidate for the longest, ongoing computational project in history. See this reference for some background.

For numbers of this special form, the number field sieve is particularly efficient and when applied to them, the technique is called the special number field sieve (SNFS). However, it is also applicable numbers with no known special form and in this case it is called the general number field sieve (GNFS).

To recap, SNFS is faster than GNFS but is applicable to only numbers of a special form. GNFS is slower than SNFS but can be applied to any number and it stands as the asymptotically fastest known algorithm for factoring large composite integers with no special form.

As of November 2002, the record-holding SNFS factorization is the 233-digit factorization of 2^773+1 and the record-holding GNFS factorization is the 158-digit factorization of a divisor of 2^953+1. Although 2^953+1 is of the special form required for SNFS, it was out of the reach of current computational resources. Various smaller factors of it had been discovered leaving the c158 co-factor which was split using GNFS.

How can I learn more about the Number Field Sieve?
A solid understanding of the continued fraction method (CFRAC), the quadratic sieve and QS variants is a very good start. Even a basic description of the number field sieve is beyond the scope of this FAQ however there are several books that provide excellent descriptions CFRAC and the QS and go further to explain at least the basics of the number field sieve. Amongst them are:

    Prime Numbers: A Computational Perspective
    by Richard Crandall and Carl Pomerance
    published by Springer Verlag
    ISBN: 0387947779, (March 2001)

    Numbers and Computer Methods for Factorization
    by Hans Riesel
    published by Springer Verlag
    ISBN: 0817637435, 2nd edition (Sept. 1994)

Various papers are available on-line including:

    The Number Field Sieve
    by A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard
    (postscript, 160K)

    The Factorization of the Ninth Fermat Number
    by A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard
    (postscript, 230K)

    Factorization of a 512-bit RSA modulus
    by S. Cavallar, B. Dodson, A.K. Lenstra, W.M. Lioen, P.L. Montgomery, B. Murphy, H.J.J. te Riele,
    K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J. Marchand, F. Morain, A. Muffet,
    C. Putnam, C. Putnam, and P. Zimmermann
    (postscript, compressed, 128K)

Studying the number field sieve can be an immensely rewarding experience. A successful implementation requires an understanding of optimization techniques, distributed computing principles, algebraic number theory, large-scale linear algebra methods, and much more. Each of these subjects is a rich field of its own.

All FAQ sections:
    System Requirements
    Running the NFSNET Client
    Communications
    About the Number Field Sieve