Even faster integer multiplication

We give a new algorithm for the multiplication of n-bit integers in the bit complexity model, which is asymptotically faster than all previously known algorithms. More precisely, we prove that two n-bit integers can be multiplied in time O(n log n K-log*(n)), where K = 8 and log* n = min {k is an element of...(kx) log <= 1}. Assuming standard conjectures about the distribution of Mersenne primes, we give yet another algorithm that achieves K = 4. The fastest previously known algorithm was due to Ftirer, who proved the existence of a complexity bound of the above form for some finite K. We show that an optimised variant of Hirer's algorithm achieves only K = 16, suggesting that our new algorithm is faster than Hirer's by a factor of 2(log)* (n). (C) 2016 Elsevier Inc. All rights reserved.