On the Complexity of Hybrid n-Term Karatsuba Multiplier for Trinomials

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

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

The n -term Karatsuba algorithm (KA) is an extension of 2-term KA, which can obtain even fewer multiplications than the original one. The existing n-term Karatsuba hybrid GF(2m) ultipliers rely on factorization of m or m-1, so that put a confinement to these schemes. In this contribution, we use a new decomposition m=nℓ+r, such that 0≤ r< n and 0≤ r< ℓ, and propose a novel n-term Karatsuba hybrid GF(2m) multiplier for an arbitrary irreducible trinomial xm+xk+1, m≥ 2k. Combined with shifted polynomial basis, a new approach (other than Mastrovito approach) is introduced to exploit the spatial correlations among different subexpressions. We investigate the explicit space and time complexities, and discuss related upper and lower bounds. As a main contribution, the flexibilities of n, ℓ and r make our proposal approaching optimal for any given m. The space complexity can achieve to m2/2+O(√11 m3/2/2), 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 a new class of trinomials. In particular, we demonstrate that the hybrid multiplier for xm+xk+1, where k is approaching m/2 , can achieve a better space-time trade-off than any other trinomials.

Original languageEnglish (US)
Article number8943958
Pages (from-to)852-865
Number of pages14
JournalIEEE Transactions on Circuits and Systems I: Regular Papers
Volume67
Issue number3
DOIs
StatePublished - Mar 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Keywords

  • Hybrid multiplier
  • n-term Karatsuba algorithm
  • optimal
  • shifted polynomial basis
  • trinomials

Fingerprint

Dive into the research topics of 'On the Complexity of Hybrid n-Term Karatsuba Multiplier for Trinomials'. Together they form a unique fingerprint.

Cite this