# Fast integer multiplication using generalized Fermat primes

1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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$. We obtain here the same result $K=4$ using simple modular arithmetic as a building block, and a careful complexity analysis. We obtain a similar result $K=4$ using an alternative somewhat simpler algorithm, which relies on arithmetic modulo generalized Fermat primes.
Keywords :
Type de document :
Pré-publication, Document de travail
2016
Domaine :

Littérature citée [26 références]

https://hal.inria.fr/hal-01108166
Contributeur : Svyatoslav Covanov <>
Soumis le : jeudi 28 janvier 2016 - 09:05:27
Dernière modification le : jeudi 11 janvier 2018 - 06:27:51
Document(s) archivé(s) le : vendredi 29 avril 2016 - 10:15:31

### Fichiers

conjfim.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01108166, version 2
• ARXIV : 1502.02800

### Citation

Svyatoslav Covanov, Emmanuel Thomé. Fast integer multiplication using generalized Fermat primes. 2016. 〈hal-01108166v2〉

### Métriques

Consultations de la notice

## 597

Téléchargements de fichiers