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 Ω(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) .

Authors

• Martin Fürer

Keywords

• FFT
• complexity
• computer arithmetic
• discrete Fourier transform
• integer multiplication