A log-log speedup for exponent one-fifth deterministic integer factorisation
David Harvey, Markus Hittmeir · Mathematics of Computation · 2021
Building on techniques recently introduced by the second author, and further developed by the first author, we show that a positive integer N N may be rigorously and deterministically factored into primes in at most \[ O ( N 1 / 5 log 16 / 5 N ( log log N ) 3 / 5 ) O\left ( \frac {N^{1/5} \log ^{16/5} N}{(\log \log N)^{3/5}}\right ) \] bit operations. This improves on the previous best known result by a factor of ( log log N ) 3 / 5 (\log \log N)^{3/5} .