On: 768-bit RSA, now officially not enough

[lmkg]

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.