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.
computer science, theory, Integer multiplication, algorithm, complexity bound, FFT
Jul 15, 2014