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 Ω(n log n) lower bound. The prevailing conjecture has always been that the complexity of an optimal algorithm is Θ(n log n). We present a major step towards closing the gap from above by presenting an algorithm running in time n log n, 2 O(log* n) .   The main result is for boolean circuits as well as for multitape Turing machines, but it has consequences to other models of computation as well.
['Martin Fürer']
Faster integer multiplication