Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast integer multiplication using generalized Fermat primes

Authors: Svyatoslav Covanov and Emmanuel Thomé
Journal: Math. Comp. 88 (2019), 1449-1477
MSC (2010): Primary 68W30; Secondary 11A41
Published electronically: July 23, 2018
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: For almost 35 years, Schönhage-Strassen's algorithm has been the fastest algorithm known for multiplying integers, with a time complexity $ O(n \cdot \log n \cdot \log \relax \log n)$ for multiplying $ n$-bit inputs. In 2007, Fürer proved that there exists $ K>1$ and an algorithm performing this operation in $ O(n \cdot \log n \cdot K^{\log ^* n})$. Recent work by Harvey, van der Hoeven, and Lecerf showed that this complexity estimate can be improved in order to get $ K=8$, and conjecturally $ K=4$. Using an alternative algorithm, which relies on arithmetic modulo generalized Fermat primes (of the form $ r^{2^{\lambda }}+1$), we obtain conjecturally the same result $ K=4$ via a careful complexity analysis in the deterministic multitape Turing model.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 11A41

Retrieve articles in all journals with MSC (2010): 68W30, 11A41

Additional Information

Svyatoslav Covanov
Affiliation: Université de Lorraine, CNRS, INRIA, LORIA, F-54000 Nancy, France

Emmanuel Thomé
Affiliation: Université de Lorraine, CNRS, INRIA, LORIA, F-54000 Nancy, France

Received by editor(s): January 27, 2016
Received by editor(s) in revised form: July 10, 2017, January 25, 2018, and March 7, 2018
Published electronically: July 23, 2018
Article copyright: © Copyright 2018 American Mathematical Society