Cryptology ePrint Archive: Report 2019/111

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

Yin Li and Shantanu Sharma and Yu Zhang and 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.

Category / Keywords: implementation / Bit-parallel multiplier, $n$-Karatsuba algorithm, shifted polynomial basis, optimal, trinomials

Original Publication (with minor differences): IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I

Date: received 3 Feb 2019, last revised 2 Dec 2019

Contact author: yunfeiyangli at gmail com

Available format(s): PDF | BibTeX Citation

Note: we add new paragraph, fix some errors

Version: 20191203:022128 (All versions of this report)

Short URL: ia.cr/2019/111


[ Cryptology ePrint archive ]