3 ms·
> "This destroyes the RSA cryptosystem" For 800-bit keys.
by 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.