Hacker News new | past | comments | ask | show | jobs | submit login

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.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: