The Number Field Sieve

The number field sieve is a new factoring algorithm with a much lower asymptotic running time estimate than previous algorithms. It was first proposed by Pollard [37] for factoring integers near perfect cubes, with the basic idea derived from the early work of ElGamal [16]. A similar idea was proposed independently by Elkies (electronic mail communication of Feb. 13, 1989) a short time later. The Pollard approach was then extended by A. Lenstra, H. Lenstra, and M. Manasse [25] to factor so-called Cunningham integers, that is integers n of the form

$$n = a^k \pm 1$$ (24)

where a is small and k is large. If we let

$$L_n(v,r) = \mbox{exp}((r + o(1))(\log n)^{v}(\log \log n)^{1-v}),$$ (25)

then the number field sieve factors Cunningham integers n in time

$$L_n(1/3,2(2/3)^{2/3}) = L_n(1/3,1.526\ldots{}).$$ (26)

(This estimate is based on several assumptions that seem reasonable but have not been proven.) This algorithm is fast not only asymptotically, but also in practice, although it is quite complicated to implement. A. Lenstra and M. Manasse have recently used it to factor F₉ = 2⁵¹² +1 in about the same amount of time that the quadratic sieve requires to factor integers of about 110 decimal digits. (F₉ has 155 decimal digits, and one prime factor of 7 decimal digits was already known. However, this did not help, since the number field sieve for Cunningham integers cannot take advantage of such auxiliary information. Thus it is a debatable point whether A. Lenstra and M. Manasse factored a 155 or a 148 decimal digit integer.)

The number field sieve can also be extended to factor general integers. At first, the only technique that could be shown to work in general was due to Buhler, H. Lenstra, and Pomerance, and it yields a running time estimate of

$$L_n(1/3,3^{2/3}) = L_n(1/3,2.080\ldots{}).$$ (27)

Recently H. Lenstra and Adleman [1] have proposed two independent techniques which lower the running time estimate to

$$L_n(1/3,4\cdot3^{-2/3}) = L_n(1/3,1.922\ldots{}).$$ (28)

Even more recently, Coppersmith [11] has proposed a modification that achieves a running time of

$$L_n(1/3,2^{1/3}\cdot3^{-1}\cdot(46+13\sqrt{13})^{1/3}) = L_n(1/3,1.901\ldots{}).$$ (29)

Although asymptotically this is still far better than other algorithms, the point at which this method would be faster than algorithms such as the quadratic sieve appears to be in the vicinity of 200 decimal digits. On the other hand, the number field sieve is a very recent invention, and so it is likely that substantial improvements might occur which would make it practical.

The number field sieve can be extended to computing discrete logarithms, as is shown in [18].