Paper 2019/111

On the Complexity of non-recursive $n$-term Karatsuba Multiplier for Trinomials

Yin Li, Shantanu Sharma, Yu Zhang, Xingpo Ma, and Chuanda Qi

Abstract

The $n$-term Karatsuba algorithm (KA) is an extension of 2-term KA, which can obtain even fewer multiplications than the original one. In this contribution, we proposed a novel hybrid $GF(2^m)$ Karatsuba multiplier using $n$-term KA for irreducible trinomials of arbitrary degree, i.e., $x^m+x^k+1$ where $m\geq2k$. We multiply two $m$-term polynomials using $n$-term KA, by decomposing $m$ into $n\ell+r$, such that $r<n, \ell$. Combined with shifted polynomial basis (SPB), a new approach other than Mastrovito approach is introduced to exploit the spatial correlation between different subexpressions. Then, exact complexity formulations for proposed multipliers are determined. Based on these formulae, we discuss the optimal choice of parameters $n, \ell$ and the effect of $k$. Some upper and lower bounds with respect to these complexities are evaluated as well. As a main contribution, the space complexity of our proposal can achieve to ${m^2}/{2}+O({\sqrt{11}m^{3/2}}/{4})$, which roughly matches the best result of current hybrid multipliers for special trinomials. Meanwhile, its time complexity is slightly higher than the counterparts, but can be improved for some special trinomials. In particular, we demonstrate that the hybrid multiplier for $x^m+x^{k}+1$, where $k$ is approaching $\frac{m}{2}$, can achieve a better space and time trade-off than any other trinomials.

Note: we add new paragraph, fix some errors