On: 768-bit RSA, now officially not enough

[ajross]

I 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 gives the complexity as O(constant ^ ((logN^1/3)*(log logN ^ 2/3)). Which grows really slowly.

[cperciva → ajross]

the 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.

[lmkg → cperciva]

Isn't that the same thing?

(n^1/3)^c = n^(c/3)

Still an exponential relationship, just a smaller constant.

[cperciva → lmkg]

Those are polynomial, not exponential.

Polynomial time: O(n^c)

GNFS time: O(c^(n^(1/3))

Exponential time: O(c^n)

[ajross → cperciva]

I'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.

[jrockway → lmkg]

And that's why it's 1000, not 2^256.

[ajross → cperciva]

My 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 → ajross]

If you had left it at the apology I would have voted you up.