"This destroyes the RSA cryptosystem"
cryptologie.net
cryptologie.net
Could somebody with more of a cryptography background explain:
1. What exactly is in the paper? My understanding is it is a faster method of factoring , but how much faster?
2. "Destroying" RSA sounds sensationalist. How accurate is that statement?
3. How likely is this to have an impact on real world uses of RSA like HTTPS?
Some discussion on Twitter https://twitter.com/ManishEarth/status/1366898044470403072
For 800-bit keys.
Note of course that polynomial time factorization doesn't mean "fast", it means feasible. So what a professor at a university can do (800bits) does not necessarily represent what can be done with someone with more money and computers (NSA, Google, AWS, ...).
Assuming this holds up of course.
That said I only did 2nd year number theory, and I did that almost 20 years ago so 50/50 I'm totally wrong
It's exponential to a sublinear function (cube root) of log N, not log N. https://en.wikipedia.org/wiki/General_number_field_sieve
> The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.