[Sniffnoy]

Note that what makes this notable is that the time bound is proven (according to the paper, anyway). N^1/5 is much slower than we normally think of GNFS as being, but the thing to note is that GNFS isn't actually proven to run that fast.

[pbsd]

Subexponential algorithms in general have long had proven running times. Dixon's method [1], in particular, has had a proven running time since 1980. The number field sieve itself has had some recent progress on that front [2].

However, those algorithms are _probabilistic_, not _deterministic_, which is what sets this linked method apart.

This algorithm, much like Pollard-Strassen before it, is pretty much irrelevant to integer factorization in practice. But it is nevertheless remarkable to see some progress on deterministic factorization after such a long time.

[1] https://doi.org/10.1090/S0025-5718-1981-0595059-1

[2] https://doi.org/10.1016/j.jnt.2017.10.019

[Pet_Ant]

Why is it irrelevant in practice? Because the probabilistic algorithms are so much better in practice?

[pbsd]

Yes. Between Pollard's rho, SQUFOF, ECM, the various sieves, etc, there is essentially no range at which this one performs better.

[Sniffnoy]

I see, thank you for the correction!