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.
Comments
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
Why is it irrelevant in practice? Because the probabilistic algorithms are so much better in practice?
Yes. Between Pollard's rho, SQUFOF, ECM, the various sieves, etc, there is essentially no range at which this one performs better.
I see, thank you for the correction!