Paper 2018/605

N-term Karatsuba Algorithm and its Application to Multiplier designs for Special Trinomials

Yin Li, Yu Zhang, Xiaoli Guo, and Chuanda Qi


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.

Note: It is a primary version and we do not submit it anywhere.

Available format(s)
Publication info
Preprint. MINOR revision.
N-term Karatsuba AlgorithmSpecific trinomialsBit-parallel Multiplier
Contact author(s)
yunfeiyangli @ gmail com
2018-06-18: received
Short URL
Creative Commons Attribution


      author = {Yin Li and Yu Zhang and Xiaoli Guo and Chuanda Qi},
      title = {N-term Karatsuba Algorithm and its Application to Multiplier designs for Special Trinomials},
      howpublished = {Cryptology ePrint Archive, Paper 2018/605},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.