# Even Faster Integer Multiplication

### (2014)

##
Abstract:

We give a new proof of Frer's bound for the cost of multiplying n-bit integers in the bit
complexity model. Unlike Frer, our method does not require constructing special coecient
rings with fast roots of unity. Moreover, we prove the more explicit bound O(n logn Klog n)
with K = 8. We show that an optimised variant of Frer's algorithm achieves only K = 16,
suggesting that the new algorithm is faster than Frer's by a factor of 2log n. Assuming stan-
dard conjectures about the distribution of Mersenne primes, we give yet another algorithm
that achieves K = 4.

##
Authors:

David Harvey,
Joris van der Hoevena,
and Grgoire Lecerfb

##
Tags:

computer science,
theory,
Integer multiplication,
algorithm,
complexity bound,
FFT

##
Date Submitted:

Jul 15, 2014

## Discussion and Questions