D. J. Bernstein
Integer factorization
Circuits for integer factorization

Historical notes on the cost-effectiveness of circuit NFS

There are many calculations for which special-purpose circuits are vastly more cost-effective than conventional computers. This is a well-known fact; it is the theme of thousands of articles in the very-large-scale-integration (VLSI) research literature.

There are two major pieces of an NFS calculation: sieving and linear algebra. There are, correspondingly, two crucial points in my October 2001 grant proposal:

For large input sizes, using conventional computers (or TWINKLE) for NFS sieving is a bad idea, because low-memory smoothness-testing circuits, such as ECM circuits, are much more cost-effective.
For large input sizes, using conventional computers for NFS linear algebra is a bad idea, because various linear-algebra circuits, such as mesh-sorting circuits, are much more cost-effective.

These are new observations; they do not appear in the previous literature.

(Starting from these observations, one can easily calculate the cost exponents for NFS, as I did in my grant proposal. Figuring out the exact cost for NFS is much more difficult.)

The June 2002 Lenstra-Shamir-Tomlinson-Tromer paper observes, correctly, that reasonably fast low-memory smoothness-testing techniques have been widely known for decades. (Of course, my grant proposal says the same thing.) The Lenstra-Shamir-Tomlinson-Tromer paper then leaps to the conclusion that the cost-effectiveness of those techniques for large input sizes was previously known. That conclusion is incorrect. For example, Silverman's cost-analysis paper and the Lenstra-Shamir TWINKLE paper in 2000 did not mention the cost-effectiveness of low-memory smoothness-testing techniques. Both papers were discussing the cost of state-of-the-art integer factorization.

The Lenstra-Shamir-Tomlinson-Tromer paper cites a 1993 paper by Coppersmith in which Coppersmith uses ECM inside NFS. The Lenstra-Shamir-Tomlinson-Tromer paper fails to point out that (as mentioned in my grant proposal) Coppersmith used ECM in a context where conventional sieving would have meant looking at a much larger volume of data. Coppersmith did not observe that ECM was better than conventional sieving in other contexts. In fact, for the first step of his algorithm, Coppersmith specifically recommended conventional sieving!

Bottom line: Papers before mine optimized their machines purely for operation count. The resulting machines are far less cost-effective than the circuits described in my paper.