Integer factorization

Circuits for integer factorization

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.

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