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.

Published in:
Siam Journal On Computing, 39, 979-1005
Presented at:
39th Annual ACM Symposium on Theory of Computing, San Diego, CA, Jun 11-13, 2007

 Record created 2010-11-30, last modified 2018-09-13

Rate this document:

Rate this document:
(Not yet reviewed)