3 ms·
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 bei
by Sniffnoy 6y ago
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 6y agoSubexponential 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 https://doi.org/10.1090/S0025-5718-1981-0595059-1 [2] https://doi.org/10.1016/j.jnt.2017.10.019 https://doi.org/10.1016/j.jnt.2017.10.019
- Sniffnoy 6y agoI see, thank you for the correction!
- Pet_Ant 6y agoWhy is it irrelevant in practice? Because the probabilistic algorithms are so much better in practice?
- pbsd 6y agoYes. Between Pollard's rho, SQUFOF, ECM, the various sieves, etc, there is essentially no range at which this one performs better.