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

*Yin Li and Yu Zhang and Xingpo Ma and Chuanda Qi*

**Abstract: **In this paper, we continue the study of bit-parallel multiplier using a $n$-term Karatsuba algorithm (KA), recently introduced by Li et al. (IEEE Access 2018). Such a $n$-term KA is a generalization of the classic KA, which can multiply two $n$-term polynomials using $O(n^2/2)$ scalar multiplications. Based on this observation, Li et al. developed an efficient bit-parallel multiplier scheme for a new special class of irreducible trinomial $x^{m}+x^{k}+1, m=nk$. The lower bound of the space complexity of their proposal is about $O(\frac{m^2}{2}+m^{3/2})$.
However, such a special type of trinomial does not always exist.
In this contribution, we investigate the space and time complexity of Karatsuba multiplier for general trinomials, i.e., $x^m+x^k+1$ where $m>2k$. We use a new decomposition that $m=n\ell+r$, where $r<n, r<\ell$.
Combined with shifted polynomial basis (SPB), a new approach other than Mastrovito approach is proposed to exploit the spatial correlation between different subexpressions. Explicit space and time complexity formulations are given to indicate the optimal choice of the decomposition. As a result, the optimal multiplier achieves nearly the same space complexity as $x^{m}+x^{k}+1, m=nk$, but it is suitable to more general trinomials.
Meanwhile, its time complexity matches or is at most $1T_X$ higher than the similar KA multipliers, where $T_X$ is the delay of one 2-input XOR gate.

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

**Date: **received 3 Feb 2019, last revised 5 Feb 2019

**Contact author: **yunfeiyangli at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **This is a sigle column version

**Version: **20190206:203423 (All versions of this report)

**Short URL: **ia.cr/2019/111

[ Cryptology ePrint archive ]