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


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

Available format(s)
Publication info
Published elsewhere. Minor revision. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I
Bit-parallel multiplier$n$-Karatsuba algorithmshifted polynomial basisoptimaltrinomials
Contact author(s)
yunfeiyangli @ gmail com
2019-12-03: last of 2 revisions
2019-02-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yin Li and Shantanu Sharma and Yu Zhang and Xingpo Ma and Chuanda Qi},
      title = {On the Complexity of non-recursive $n$-term Karatsuba Multiplier for Trinomials},
      howpublished = {Cryptology ePrint Archive, Paper 2019/111},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.