5 ms·
"This destroyes the RSA cryptosystem"
- chovybizzass 6y agono it doesn't.
- notamy 6y agoSee earlier discussion: https://news.ycombinator.com/item?id=26321962 https://news.ycombinator.com/item?id=26321962
- cmeacham98 6y agoI 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?
- adamnemecek 6y agoCan we appreciate that a guy in his 70’s is memeing pretty hard?
- sp332 6y agoInteresting, but there is a newer-dated version on his actual website https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf 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 https://twitter.com/ManishEarth/status/1366898044470403072
- lisper 6y ago> "This destroyes the RSA cryptosystem" For 800-bit keys.
- olliej 6y agoI 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.
- dataflow 6y agoI think by "sub-exponential" you meant "faster than the known fastest", because GNFS is already sub-exponential.
- olliej 6y agoIsn'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
- dataflow 6y agoIf 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 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.
- yesenadam 6y agoThis adds nothing (except an "e") to the link posted 4 hours ago, with 100+ comments https://news.ycombinator.com/item?id=26321962 https://news.ycombinator.com/item?id=26321962