Efficient Binary Polynomial Multiplication Based on Optimized Karatsuba Reconstruction

Christophe Negre 1
1 DALI - Digits, Architectures et Logiciels Informatiques
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, UPVD - Université de Perpignan Via Domitia
Abstract : At Crypto 2009 Bernstein proposed two optimized Karatsuba formulas for binary polynomial multiplication. Bernstein obtained these optimizations by re-expressing the reconstruction of one or two recursions of the Karatsuba formula. In this paper we present a generalization of these optimizations. Specifically, we optimize the reconstruction of s recursions of the Karatsuba formula for s >= 1. To reach this goal, we express the recursive reconstruction through a tree and re-organize this tree to derive an optimized recursive reconstruction of depth $s$. When we apply this approach to a recursion of depth s=\log_2(n) we obtain a parallel multiplier with a space complexity of 5.25 n^(\log_2(3))+O(n) XOR gates and n^(\log_2(3)) AND gates and with a delay of 2log_2(n) D_X+D_A.
Type de document :
Article dans une revue
Journal of Cryptographic Engineering, Springer, 2014, 4 (2), pp.91--106. 〈10.1007/s13389-013-0066-2〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00724778
Contributeur : Christophe Negre <>
Soumis le : mercredi 22 août 2012 - 15:53:29
Dernière modification le : samedi 25 novembre 2017 - 10:16:11
Document(s) archivé(s) le : vendredi 23 novembre 2012 - 02:26:33

Fichier

ext-4way-bernstein15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Christophe Negre. Efficient Binary Polynomial Multiplication Based on Optimized Karatsuba Reconstruction. Journal of Cryptographic Engineering, Springer, 2014, 4 (2), pp.91--106. 〈10.1007/s13389-013-0066-2〉. 〈hal-00724778〉

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

575