D. J. Bernstein
Integer factorization
Circuits for integer factorization

Figuring out the exact cost of NFS

My October 2001 grant proposal explains a sample NFS circuit. My grant proposal then briefly points out many ways that the circuit can be changed: sieving via Schimmler's algorithm, for example, or using Lanczos-type algorithms instead of Wiedemann's algorithm.

My grant proposal asks three questions about these circuits. In short: Exactly how cost-effective are these circuits for specific input sizes? Will users have to switch to larger keys? Will users have to switch to keys 3 times larger?

(The number 3 here is based on my analysis of the cost exponents of these circuits. Beware that statements about the cost exponent, when accurately formulated, use o(1), so they say nothing about specific input sizes such as 1024 bits.)

The objective of the grant is to figure out the most cost-effective circuit for, e.g., 1024-bit inputs. My sample circuit is certainly not the best one; finding the best one is a huge project, involving a careful combination of number theory and circuit design.

(ECM is obviously not optimal, for example, because it is slower than early-abort ECM. The exponents are the same, but the exponents are certainly not a complete description of performance! I am investigating the following structure for sieving: mesh sieving with small primes, abort, trial division with tiny primes, abort, rho, abort, rho, abort, etc., ECM, abort, ECM, abort, etc. There are a huge number of parameters to tune here.)

The National Science Foundation has funded the grant for summer 2002, summer 2003, and summer 2004. Results will be announced on these web pages.