Chennai Mathematical Institute


Fast Algorithms for Integer Multiplication
Ramprasad Saptharishi
Chennai Mathematical Institute.


One of the most fundamental problems in computational algebra is the task of multiplying two N-bit integers. A natural question to ask is how fast one could multiply integers. An important breakthrough in algorithms for multiplying integers was the algorithm of Schonhage-Strassen that achieves a time complexity of O(N log N loglog N). The main idea in their approach was to use polynomial multiplications and Fourier Transforms. This algorithm remained the best for about 35 years until Martin Furer gave a faster algorithm in 2007, achieving a time complexity of O(N log N 2^{O(log*N)}). This remarkable result however uses complex numbers and therefore involves tedious error analysis. One could ask if a similar time complexity can be achieved through just modular computation. This talk will outline our results to say that the answer is indeed yes.

This is joint work with Anindya De, Chandan Saha and Piyush P Kurur of IIT Kanpur.