Welcome to the resource topic for 2018/605
Title:
N-term Karatsuba Algorithm and its Application to Multiplier designs for Special Trinomials
Authors: Yin Li, Yu Zhang, Xiaoli Guo, Chuanda Qi
Abstract:In this paper, we propose a new type of non-recursive Mastrovito multiplier for GF(2^m) using a n-term Karatsuba algorithm (KA), where GF(2^m) is defined by an irreducible trinomial, x^m+x^k+1, m=nk. We show that such a type of trinomial combined with the n-term KA can fully exploit the spatial correlation of entries in related Mastrovito product matrices and lead to a low complexity architecture. The optimal parameter n is further studied. As the main contribution of this study, the lower bound of the space complexity of our proposal is about O(\frac{m^2}{2}+m^{3/2}). Meanwhile, the time complexity matches the best Karatsuba multiplier known to date. To the best of our knowledge, it is the first time that Karatsuba-based multiplier has reached such a space complexity bound while maintaining relatively low time delay.
ePrint: https://eprint.iacr.org/2018/605
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 .