A babystep-giantstep method for faster deterministic integer factorization

Abstract

In 1977, Strassen presented a deterministic and rigorous algorithm for solving the problem of computing the prime factorization of natural numbers $N$. His method is based on fast polynomial arithmetic techniques and runs in time $\tilde{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 \[ \widetilde{O}\left(N^{1/4}\exp(-C\log N/\log\log N)\right). \]

20 pages

References in corpus (1)

• Deterministic factorization of sums and differences of powers

Cited by in corpus (7)

• A log-log speedup for exponent one-fifth deterministic integer factorisation
• A time-space tradeoff for Lehman's deterministic integer factorization method
• Integer factorization as subset-sum problem
• Smooth Subsum Search: A heuristic for practical integer factorization
• Supersingular $j$-invariants and the Class Number of $\mathbb{Q}(\sqrt{-p})$
• Canonical form of modular hyperbolas with an application to integer factorization
• A reduction of integer factorization to modular tetration