Integer factorization

Circuits for integer factorization

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.