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

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.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
N-term Karatsuba AlgorithmSpecific trinomialsBit-parallel Multiplier
Contact author(s)
yunfeiyangli @ gmail com
History
2018-06-18: received
Short URL
https://ia.cr/2018/605
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/605,
      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{https://eprint.iacr.org/2018/605}},
      url = {https://eprint.iacr.org/2018/605}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.