D. J. Bernstein
Integer factorization
Circuits for integer factorization

The balance between sieving and linear algebra

There are many parameters in NFS: dials that can be adjusted to affect the speed of the algorithm in complicated ways. The most important parameter is the ``prime bound,'' usually called y.

As y increases from ``tiny'' to ``standard,'' the cost of sieving drops down to a smallest possible value, while the cost of linear algebra rises. As y increases past standard, the cost of sieving starts rising again, and keeps rising, while the cost of linear algebra also rises.

Sieving speed is important

In the context of TWINKLE, Lenstra and Shamir claimed that sieving speedups had limited value, because linear algebra by itself was a bottleneck.

That claim is obviously false. One can always decrease y to reduce the cost of linear algebra until sieving and linear algebra are in balance.

Section 4.3 of the June 2002 Lenstra-Shamir-Tomlinson-Tromer paper says that ``in past factorization experiments'' linear algebra was never a bottleneck. This is a content-free observation. Linear algebra is never a bottleneck.

Linear-algebra speed is important

The Lenstra-Shamir-Tomlinson-Tromer paper claims that linear-algebra speedups have limited value, because sieving by itself is a bottleneck: ``the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve.''

That claim is also false, at least for large numbers. (It is true for Pomerance's optimized version of conventional NFS, but circuit NFS is much more cost-effective than conventional NFS for large numbers.) As stated in my October 2001 grant proposal, the optimal value of y for circuit NFS is substantially smaller than standard, so one can increase y to reduce the cost of sieving until sieving and linear algebra are in balance.

Perhaps someday we'll discover better linear-algebra methods. Perhaps the cost of linear algebra will become unnoticeable for standard values of y; then sieving by itself will be a bottleneck. However, as stated in my grant proposal, the current situation for large numbers is that linear algebra is relatively difficult; as a consequence, when parameters are chosen properly, sieving and linear algebra are in balance.