Title

All known methods for integer multiplication (except the trivial school method) are based on some version of the Chinese Remainder Theorem. Most methods reduce integer multiplication to fast polynomial multiplication, which is a scheme for the evaluation of polynomials, multiplication of their values, followed by interpolation. For more than 35 years, the fastest known method for integer multiplication has been the Schönhage-Strassen algorithm. It is based on the fast Fourier transform (FFT) and runs in time O(n log n log log n). Since then, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is O(n log n). A recent multiplication algorithm with a running time of n log n exp(O(log* n) is presented. It is a step towards closing the gap from above. The running time bound holds for multitape Turing machines. The same bound is valid for the size of boolean circuits.