Cryptology ePrint Archive: Report 2019/111

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 ]