On the Complexity of Hybrid $n$ -Term Karatsuba Multiplier for Trinomials
Yin Li, Shantanu Sharma, Yu Zhang, Xingpo Ma, Chuanda Qi · IEEE Transactions on Circuits and Systems I Regular Papers · 2019
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) multipliers 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 ≤ rm) multiplier for an arbitrary irreducible trinomial xm+ xk+ ℓ, 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 m2/2 + O(√11 m3/2/2), which roughly matches the best result optimal for any given m. The space complexity can achieve to 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.