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(nlog nloglog n). Under certain restrictive conditions, there is a corresponding Ω(nlog n) lower bound. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is Θ(nlog 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 nlog n\,2O(log^*n). The running time bound holds for multitape Turing machines. The same bound is valid for the size of Boolean circuits.