(with Joris van der Hoeven and Grégoire Lecerf)
J. Complexity 36 (2016), 1–30 (DOI).
2016 Journal of Complexity Best Paper Award.
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.