Integer Multiplication is one of the most active fields of research in Computer Science and Mathematics and we are on the verge of finding the ultimate answer in this path. Everything started in 1960 and things proceeded in 3 major progress over the years.

The must read research papers on Integer Multiplication are (in order):

We will go through the details of each of the above papers along with links using which you can access them and read it yourself.

Karatsuba Algorithm

• Published at: Dokl Akad Nauk SSSR (Journal), 1962, Volume 145, Number 2
• Date: 1962
• Author: A. Karatsuba, Yu. Ofman
• Affiliation: Moscow State University
• Citations: 583
• Link: Paper by MathNet (Russian)
• Article: Karatsuba Algorithm by OpenGenus

This algorithm will always be remembered as the first algorithm to break the O(N²) barrier for Integer Multiplication. It has an time complexity of O(N^1.58) and is a must read if you want to understand how Integer Multiplication can be optimized.

Schonhage Strassen algorithm

• Published at: Computing Journal
• Date: 1971
• Author: A. Schonhage, Volker Strassen
• Affiliation: University of Konstanz, University of Zurich
• Citations: 547
• Link: Paper by Springer

This algorithm held the record of being the Fastest Integer Multiplication algorithm for 36 years from 1971 to 2007. This is a must read. It achieved a time complexity of O(N * logN * loglogN) by using ideas of Fast Forier Transform (FTT).

Faster Integer Multiplication by Martin Furer

• Published at: 39th annual ACM Symposium on Theory of Computing (STOC)
• Date: 11th July 2007
• Journal: SIAM Journal on Computing, Vol. 39 Issue 3, 979–1005, 2009
• Author: Martin Furer
• Affiliation: Pennsylvania State University
• Citations: 493
• Link: Archieved paper (PDF) by Pennsylvania State University

This was the first paper to break the record held by Schonhage Strassen algorithm for 36 years. This algorithm is of great theoretical interest as it brought the time complexity of Integer Multiplication of two N digit numbers to O(N logN 2 ^O(log*N)) time.

This algorithm is not used practically and there are several improvements over this.

DKSS Algorithm

• Published at: Proceedings of the fortieth annual ACM symposium on Theory of computing
• Date: May 2008
• Author: Anindya De, Piyush P. Kurur, Chandan Saha , Ramprasad Saptharishi
• Affiliation: Indian Institute of Technology, Kanpur and Chennai Mathematical Institute, India
• Citations: 53
• Link: Paper by ACM Digital Library

This algorithm is an alternative to Furer's algorithm and achieves the same time complexity but by using Modular Arithmetic as its central idea. This is much simpler than Furer's algorithm and one must give it a shot.

Even Faster Algorithm

• Published at: Journal of Complexity, 2016 - Elsevier
• Date: 2015
• Author: David Harvey, Joris van der Hoeven, Gregoire Lecerf
• Affiliation: French National Center for Scientific Research
• Citations: 109
• Link: Paper on ArXiv

This paper improves over Furer's Algorithm and improves the constant involved by limiting it. Though there has not been any significant change in the time complexity but it takes a simpler approach and gives a tighter bound on it.

It improves the time complexity to O(N logN 2^{3 logN}). With further improvements, it has been proved to be reduced to O(N logN 2^{2 log}N).

Fast arithmetic for faster integer multiplication

• Published at: CoRR, 2015 - pdfs.semanticscholar.org
• Date: 2015
• Author: Svyatoslav Covanov, Emmanuel Thome
• Affiliation:
• Citations: 8
• Link: Paper on ArXiv

This paper provides a modified version of the legendary Furer's Algorithm but it achieves the same time complexity. The other issues of Furer's Algorithm like impractical for real use still exist with this method.

The purpose is to show that there are multiple approaches like Furer's Algorithm.

Fast integer multiplication using generalized Fermat primes

• Published at: Mathematics of Computation by AMS
• Date: 2016
• Author: Svyatoslav Covanov, Emmanuel Thome
• Affiliation: INRIA Nancy
• Citations: 15
• Link: Paper on ArXiv

This is a new algorithm based on Fermat primes and achieves a time complexity of O(N logN 2^{2 log*N}). This is same as the time complexity achieved by David Harvey, Joris van der Hoeven and Gregoire Lecerf in 2015 but with a different approach.

Integer multiplication in time O(N logN)

• Published at: hal.archives-ouvertes.fr
• Date: 2019
• Author: D Harvey, J Van Der Hoeven
• Affiliation: French National Center for Scientific Research
• Citations: 22
• Link: Paper by HAL

This is expected to resolve this fundamental operation by providing the most optimal algorithm. If this happens to be the case, Integer Multiplication will be one of the few domains that we have conquered completely. It performs Integer Multiplication for two N digits number in O(N logN) time.

These are the papers that you should read and understand to understand how we have improved Integer Multiplication over the years and now in 2020, we are on the verge of closing this domain once for all with the most optimal approach permissible in our Universe.