5 ms·
Only 2000 compute years of a single AMD 2.2GHz were reported to be used. Using the rough estimate of 9GFlops for that chip, the current top supercomputer (that
by timf 17y ago
Only 2000 compute years of a single AMD 2.2GHz were reported to be used. Using the rough estimate of 9GFlops for that chip, the current top supercomputer (that we know of) is very roughly 200,000 times as powerful.
The paper estimates 1024 would be "about a thousand times harder". 1000 times harder than 2000 compute years on that chip is roughly ten compute years on that supercomputer. Closing in...
1024 is widely not recommended anymore, though.
- niyazpk 17y agoI don't understand why 1024 bits is just a thousand times harder than 768 bits. Shouldn't it be like 2^256 times harder?
- timf 17y agoAs I am in severe 'back of the envelope' mode, I did not investigate that claim. But I think they refer to footnote 21 for the estimate: http://people.csail.mit.edu/tromer/papers/factorest.pdf http://people.csail.mit.edu/tromer/papers/factorest.pdf
- ajross 17y agoI don't pretend to understand the deep details, but the core point is that the GNSF algorithm is exponential in the bit length of the number being factored, but the exponent turns out to be distressingly small. Edit: http://en.wikipedia.org/wiki/General_number_field_sieve http://en.wikipedia.org/wiki/General_number_field_sieve gives the complexity as O(constant ^ ((logN^1/3)*(log logN ^ 2/3)). Which grows really slowly.
- cperciva 17y agothe GNSF algorithm is exponential in the bit length of the number being factored No. First, it's GNFS, not GNSF; and second, it's approximately exponential in the cube root of the bit length, not exponential in the bit length.
- ajross 17y agoMy profuse and abject apologies for transposing those glyphs. I can't imagine how that would have happened. Maybe you could apply your expertise a little and give us a better explanation than mine instead of criticizing my spelling? I didn't claim to understand the deep details, but frankly your sniping is helping even less.
- btilly 17y agoIf you had left it at the apology I would have voted you up.
- lmkg 17y agoIsn't that the same thing? (n^1/3)^c = n^(c/3) Still an exponential relationship, just a smaller constant.
- jrockway 17y agoAnd that's why it's 1000, not 2^256.
- cperciva 17y agoThose are polynomial, not exponential. Polynomial time: O(n^c) GNFS time: O(c^(n^(1/3)) Exponential time: O(c^n)
- ajross 17y agoI'm still not understanding where your criticism is directed. GNFS (see? no typo this time. Do I get a cookie?) is quite clearly outside of PTIME, though I'm not sure to which definitions of SUBEXP and EXPTIME it belongs. Thus RSA remains an algorithm which is infeasible for tractable key sizes, even if the early guesses of 512-1024 bits turned out to be wrong.