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.