Faster Integer Multiplication 论文

摘要

Abstract. 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. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication 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 2O(log ∗ n). The running time bound holds for multitape Turing machines. The same bound is valid for the size of boolean circuits.