# [Resource Topic] 2019/111: On the Complexity of non-recursive $n$-term Karatsuba Multiplier for Trinomials

Welcome to the resource topic for 2019/111

Title:
On the Complexity of non-recursive n-term Karatsuba Multiplier for Trinomials

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

Abstract:

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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.