A babystep-giantstep method for faster deterministic integer factorization

Source abstract

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 ).$$