Faster Integer Multiplication

For more than 35 years, the fastest known method for integer multiplication has been the Schonhage-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 n2(O)(log* n). The running time bound holds for multitape Turing machines. The same bound is valid for the size of Boolean circuits.