3 ms·
I think by "sub-exponential" you meant "faster than the known fastest", because GNFS is already sub-exponential.
by dataflow 6y ago
I 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.