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

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.