Integer factorization

Circuits for integer factorization

For example, in 1998, EFF built a $130000 machine that searched the DES key space in approximately 800000 seconds. The cost of this computation was approximately 104000000000 dollar-seconds; 104000000000 is the product of 130000 and 800000.

A DES key search is perfectly parallelizable. For example, EFF could instead have built a $260000 machine that searched the DES key space in approximately 400000 seconds, or a $2600000 machine that searched the DES key space in approximately 40000 seconds. The cost of the computation would still have been approximately 104000000000 dollar-seconds.

It is, of course, easier to say ``104000000000 dollar-seconds divided pretty much any way you want'' than to say ``800000 seconds for $130000, or 400000 seconds for $260000, or 200000 seconds for $520000, or 100000 seconds for $1040000, or ...'' A single number is easier to read and easier to write than a gigantic table of numbers. Consequently, in my grant proposal, I phrased many of my results in terms of computation cost.

The June 2002 Lenstra-Shamir-Tomlinson-Tromer paper
states that computation cost is a ``non-standard cost function''
and a ``new cost function.''
These statements are false;
they reflect an astonishing level of ignorance of the literature.
Computation cost (often called ``AT'' for the product of area and time,
or the ``price-performance ratio'')
is one of the most popular metrics,
perhaps *the* most popular metric,
in the VLSI research literature.

Even more troublesome is the implicit assertion
in the Lenstra-Shamir-Tomlinson-Tromer paper that
one should not use computation cost in comparing different NFS machines.
In fact,
comparing the computation cost of these machines
leads to *exactly* the same conclusions as
comparing time and comparing hardware cost.

Similarly, in a 15 March 2002 article, Bruce Schneier says that my improvements ``are more a result of redefining efficiency than anything else.'' That is simply not true.

To avoid further terminological debates, I have gone back to big redundant tables of time and hardware cost in these web pages. The conclusions are, of course, identical to the conclusions in my grant proposal.