Abstract
At Crypto 2009, 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 (HAL00724778) 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 3log_3(n)D_X+D_A. This improves the previous best known results regarding space complexity of~\cite{murat-3way} and reaches the same time complexity as the the best known approach (Fan-et al. 2010).