Efficient multiplication in finite field extensions of degree 5

Nadia El Mrabet 1 Guillevic Aurore * Sorina Ionica 2
* Auteur correspondant
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Résumé : Pour les extensions de degré 2 et 3, les méthodes de Karatsuba et Toom-Cook permettent de calculer une multiplication dans l'extension avec 3 et 5 multiplications dans le corps de base, respectivement. Pour les extensions de degré 5, les formules de Montgomery calculent la multiplication avec 13 multiplications dans le corps de base. Nous avons proposé une méthode qui calcule la multiplication dans $\F_{p^5}$ avec $9$ multiplications dans $\F_p$. Notre méthode est basée sur une intérpolation de Newton et utilise un nombre plus grand d'additions dans $\F_p$ que la méthode de Montgomery. Néanmoins, notre implémentation montre que nos formules sont plus rapides que celle de Montgomery lorsqu'on travaille avec des nombres de taille cryptographique.
Type de document :
Article dans une revue
Progress in Cryptology-Africacrypt 2011, Springer, 2011, pp.188-205. 〈http://www.springerlink.com/content/54781rj7n24p2mxl/〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00609920
Contributeur : Sorina Ionica <>
Soumis le : mercredi 20 juillet 2011 - 15:03:03
Dernière modification le : mardi 22 mai 2018 - 20:40:06

Identifiants

  • HAL Id : inria-00609920, version 1

Collections

Citation

Nadia El Mrabet, Guillevic Aurore, Sorina Ionica. Efficient multiplication in finite field extensions of degree 5. Progress in Cryptology-Africacrypt 2011, Springer, 2011, pp.188-205. 〈http://www.springerlink.com/content/54781rj7n24p2mxl/〉. 〈inria-00609920〉

Partager

Métriques

Consultations de la notice

334