Efficient Binary Polynomial Multiplication Based on Optimized Karatsuba Reconstruction - Archive ouverte HAL Access content directly
Journal Articles Journal of Cryptographic Engineering Year : 2014

Efficient Binary Polynomial Multiplication Based on Optimized Karatsuba Reconstruction

(1)
1

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.
Fichier principal
Vignette du fichier
ext-4way-bernstein15.pdf (298.49 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00724778 , version 1 (22-08-2012)

Identifiers

Cite

Christophe Negre. Efficient Binary Polynomial Multiplication Based on Optimized Karatsuba Reconstruction. Journal of Cryptographic Engineering, 2014, 4 (2), pp.91--106. ⟨10.1007/s13389-013-0066-2⟩. ⟨hal-00724778⟩
519 View
1001 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More