Lucky's 1024-bit post [was: RE: objectivity and factoring analysis]

Wei Dai weidai at
Wed Apr 24 15:30:26 EDT 2002

I have one other question about the panel analysis. Why did it focus only 
on the linear algebra part of the NFS algorithm? I would like to know, 
given the same assumption on the factor base size (10^9), how much would 
it cost to build a machine that can perform the relationship finding phase 
of the algorithm in the same estimated time frame (i.e. months)?

Using a factor base size of 10^9, in the relationship finding phase you
would have to check the smoothness of 2^89 numbers, each around 46 bits
long. (See Frog3's analysis posted at  
Those numbers look correct to me.)  If you assume a chip that can check
one number per microsecond, you would need 10^13 chips to be able to
complete the relationship finding phase in 4 months. Even at one dollar
per chip this would cost ten trillion dollars (approximately the U.S. 

So it would seem that it's still not possible for even a major government
to factor 1024-bit keys within an operationally relevant time frame unless
it was willing to devote most of its national income to the effort.

BTW, if we assume one watt per chip, the machine would consume 87 trillion
kWh of eletricity per year. The U.S. electricity production was only 3.678 
trillion kWh in 1999.

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list