Fast integer multiplication using generalized Fermat primes

Svyatoslav Covanov 1 Emmanuel Thomé 1
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 · log n · log 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 · log n · 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, we obtain conjecturally the same result K = 4 via a careful complexity analysis in the deterministic multitape Turing model.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, In press, 〈10.1090/mcom/3367 〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01108166
Contributeur : Svyatoslav Covanov <>
Soumis le : vendredi 13 avril 2018 - 15:18:20
Dernière modification le : mardi 18 décembre 2018 - 16:18:26

Fichiers

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

Identifiants

Citation

Svyatoslav Covanov, Emmanuel Thomé. Fast integer multiplication using generalized Fermat primes. Mathematics of Computation, American Mathematical Society, In press, 〈10.1090/mcom/3367 〉. 〈hal-01108166v4〉

Partager

Métriques

Consultations de la notice

171

Téléchargements de fichiers

94