Wei Dai writes: > 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 > http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01833.html. > 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. > GDP).
This is probably not the right way to approach the problem. Bernstein's relation-finding proposal to directly use ECM on each value, while asymptotically superior to conventional sieving, is unlikely to be cost-effective for 1024 bit keys. Better to extrapolate from the recent sieving results. http://citeseer.nj.nec.com/cavallar00factorization.html is the paper from Eurocrypt 2000 describing the first 512 bit RSA factorization. The relation-finding phase took about 8000 MIPS years. Based on the conventional asymptotic formula, doing the work for a 1024 bit key should take about 10^7 times as long or 80 billion MIPS years. For about $200 you can buy a 1000 MIPS CPU, and the memory needed for sieving is probably another couple of hundred dollars. So call it $500 to get a computer that can sieve 1000 MIPS years in a year. If we are willing to take one year to generate the relations then ($500 / 1000) x 8 x 10^10 is $40 billion dollars, used to buy approximately 80 million cpu+memory combinations. This will generate the relations to break a 1024 bit key in a year. If you need it in less time you can spend proportionately more. A $400 billion dollare machine could generate the relations in about a month. This would be about 20% of the current annual U.S. federal government budget. However if you were limited to a $1 billion budget as the matrix solver estimate assumed, the machine would take 40 years to generate the relations. > 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 $40 billion, 1-year sieving machine draws on the order of 10 watts per CPU so would draw about 800 megawatts in total, adequately supplied by a dedicated nuclear reactor. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
