A babystep-giantstep method for faster deterministic integer factorization
Markus Hittmeir · Mathematics of Computation · 2017
In 1977, Strassen presented a deterministic and rigorous algorithm for solving the problem of computing the prime factorization of natural numbers N N . His method is based on fast polynomial arithmetic techniques and runs in time O ~ ( N 1 / 4 ) \widetilde {O}(N^{1/4}) , which has been state of the art for the last forty years. In this paper, we will combine Strassen’s approach with a babystep-giantstep method to improve the currently best known bound by a superpolynomial factor. The runtime complexity of our algorithm is of the form \[ O ~ ( N 1 / 4 exp ( − C log N / log log N ) ) . \widetilde {O}\left (N^{1/4}\exp (-C\log N/\log \log N)\right ). \]