Fast arithmetic for faster integer multiplication

Svyatoslav Covanov 1 Emmanuel Thomé 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
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 multi-plying n-bit inputs. In 2007, Fürer proved that there ex-ists K > 1 and an algorithm performing this operation in O(n · log n · K log * n). Recent work showed that this com-plexity estimate can be made more precise with 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 rely on a conjecture about the existence of sufficiently many primes of a certain form.
Liste complète des métadonnées

https://hal.inria.fr/hal-01108166
Contributeur : Svyatoslav Covanov <>
Soumis le : jeudi 22 janvier 2015 - 21:01:41
Dernière modification le : vendredi 29 janvier 2016 - 01:06:46
Document(s) archivé(s) le : jeudi 23 avril 2015 - 10:30:31

Fichiers

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

Identifiants

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

Citation

Svyatoslav Covanov, Emmanuel Thomé. Fast arithmetic for faster integer multiplication. 2015. <hal-01108166v1>

Partager

Métriques

Consultations de
la notice

361

Téléchargements du document

174