(with Joris van der Hoeven and Grégoire Lecerf)
J. Complexity 36 (2016), 1–30 (DOI).
arXiv preprint (July 2014).
HAL preprint (July 2014).
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 Klog* n), where K = 8. 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 Fürer, who proved the existence of a complexity bound of the above form for some finite K. We show that an optimised variant of Fürer's algorithm achieves only K = 16, suggesting that our new algorithm is faster than Fürer's by a factor of 2log* n.