N-Term Karatsuba Algorithm and Its Application to Multiplier Designs for Special Trinomials

作者：Li, Yin^*; Zhang, Yu; Guo, Xiaoli; Qi, Chuanda

来源：IEEE Access, 2018, 6: 43056-43069.

DOI：10.1109/ACCESS.2018.2859451

• N-term Karatsuba algorithm
• specific trinomials
• bit-parallel multiplier

In this paper, we propose a newtype of non-recursive Mastrovito multiplier for GF(2 (m)) using an 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 paper, the lower bound of the space complexity of our proposal is about O (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 a relatively low time delay.

• 出版日期2018
• 单位信阳师范学院