This adds nothing (except an "e") to the link posted 4 hours ago, with 100+ comments https://news.ycombinator.com/item?id=26321962

See earlier discussion: https://news.ycombinator.com/item?id=26321962

I can barely understand parts of the math in the paper and the abstract is no help.

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?

Interesting, but there is a newer-dated version on his actual website https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9... and the performance numbers are not as good. Also the abstract there doesn't have the quote from the title. My best guess is that someone tampered with it, added the joke, and uploaded it to ePrint?

Some discussion on Twitter https://twitter.com/ManishEarth/status/1366898044470403072

> "This destroyes the RSA cryptosystem"

For 800-bit keys.

I think the argument was that it represents a sub-exponential factorization algorithm, so while he demonstrates with 800, it is ostensibly broken at above that.

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.

I think by "sub-exponential" you meant "faster than the known fastest", because GNFS is already sub-exponential.

Isn't gnfs exponential to logN? although as I type that I realize that is clearly lower than x^N, it is still exponential albeit to length rather than value.

That said I only did 2nd year number theory, and I did that almost 20 years ago so 50/50 I'm totally wrong

If it was exponential to log N then the exp and the log would cancel.

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.