D. J. Bernstein
Integer factorization
Circuits for integer factorization

The notion of computation cost

In my October 2001 grant proposal, I defined the cost of a computation as the product of the time taken by the computation and the cost of the hardware used for the computation.

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.