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

Yin Li; Yu Zhang; Xiaoli Guo; Chuanda Qi

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 $G F (2^{m})$ using a $n$ -term Karatsuba algorithm (KA), where $G F (2^{m})$ is defined by an irreducible trinomial, $x^{m} + x^{k} + 1, m = n k$ . 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 Algorithm Specific trinomials Bit-parallel Multiplier
Contact author(s): yunfeiyangli @ gmail com
History: 2018-06-18: received
Short URL: https://ia.cr/2018/605
License: 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},
      url = {https://eprint.iacr.org/2018/605}
}