# Even faster integer multiplication

(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).

## Abstract

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.
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 2^{log* n}.

Back to the main page