1 Improved Three-Way Split Approach for Binary Polynomial Multiplication Based on Optimized Reconstruction
Christophe Négre · 2013
At Crypto 2009 [1], Bernstein initiated an optimization of Karatsuba formula for binary polynomial multiplication by reorganizing the computations in the reconstruction part of two recursions of the formula. This approach was generalized in [10] to an arbitrary number of recursions resulting in the best known bit parallel multiplier based on Karatsuba formula. In this paper we extend this approach to three-way split formula: we first reorganize two recursions and then extend this re-organization to an arbitrary number s of recursions. We obtain a parallel multiplier with a space complexity of 4.68 n log 3 (6) +O(n) XOR gates and n log 3 (6) AND gates and a delay of 3 log 3 (n)D⊕+D⊗. This improves the previous best known results regarding space complexity of [2] and reaches the same time complexity as the the best known approach [4].