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.
ePrint: https://eprint.iacr.org/2019/111
See all topics related to this paper.
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.
For more information, see the rules for Resource Topics .