Schnorr's factorization algorithm

C.P. Schnorr, a famous mathematical cryptographer (the inventor of Schnorr signatures), has just released a new paper claiming a polynomial-time factorization algorithm which he says represents a significant improvement on attacking RSA:

I haven't seen discussions of this on m.d.s.p, cabfpub, or Scott Aaronson's blog. Has anyone seen an assessment of this by a knowledgeable number theorist?


This is the first I've heard of it, but it does look pretty new and it probably takes some time for the experts to dig into it.

I do wonder if it might be related to why the NSA recently recommended a minimum of 3072 bits for RSA keys. That's just complete speculation, though.

There seems to be some speculation on Twitter that this is an outdated draft, and the abstract may be misleading.


If the algorithm is effective, a misinformation campaign about its effectiveness or correctness, or completeness, or simply telling that it is an old stuff has high value.

There's some further discussion over on Crypto StackExchange:

1 Like

16 kilobit keys should be fairly safe for now

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.