3 versus 1.17

The 3.009...+o(1) factor can be viewed as follows:

1. a factor 1.10395...+o(1) switching from conventional NFS as described in the literature to Pomerance's April 2002 optimized version of conventional NFS;
2. an extra factor 2.33685...+o(1) switching from Pomerance's optimized version of conventional NFS to circuit NFS sieving combined with conventional NFS linear algebra; and
3. an extra factor 1.16640...+o(1) switching from circuit NFS sieving combined with conventional NFS linear algebra to complete circuit NFS.

The June 2002 Lenstra-Shamir-Tomlinson-Tromer paper asserts that the asymptotic improvement from circuits is ``to a lesser degree than previously claimed: for a given cost, the new method can factor integers that are 1.17 times larger (rather than 3.01).'' Many people have concluded that the Lenstra-Shamir-Tomlinson-Tromer paper disputes the calculations in my grant proposal, and that I might have made a mistake in my calculations.

In fact, the Lenstra-Shamir-Tomlinson-Tromer paper does not dispute any of my calculations. It does not claim that circuits are less cost-effective (slower or larger) than stated in my grant proposal. It does not claim that conventional NFS is competitive with circuit NFS. What it claims is that we already had fairly scary circuits: namely, circuit NFS sieving combined with conventional NFS linear algebra. This is revisionist history, not a technical dispute.