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.
MSC (2010): Primary 68W30; Secondary 11A41
DOI: https://doi.org/10.1090/mcom/3367
Published electronically: July 23, 2018
Full-text PDF

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
Email: svyatoslav.covanov@loria.fr

Emmanuel Thomé
Affiliation: Université de Lorraine, CNRS, INRIA, LORIA, F-54000 Nancy, France
Email: emmanuel.thome@inria.fr

DOI: https://doi.org/10.1090/mcom/3367
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

American Mathematical Society