Faster Integer Multiplication

For more than 35 years, the fastest known method for integer multiplication has been the Schönhage–Strassen algorithm running in time $O(n\log n\log\log n)$. Under certain restrictive conditions, there is a corresponding $\Omega(n\log n)$ lower bound. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is $\Theta(n\log n)$. We take a major step towards closing the gap between the upper bound and the conjectured lower bound by presenting an algorithm running in time $n\log n\,2^{O(\log^*n)}$. The running time bound holds for multitape Turing machines. The same bound is valid for the size of Boolean circuits.