Paper 2016/694

Mastrovito Form of Non-recursive Karatsuba Multiplier for All Trinomials

Yin Li, Xingpo Ma, Yu Zhang, and Chuanda Qi

Abstract

We present a new type of bit-parallel non-recursive Karatsuba multiplier over $GF(2^m)$ generated by an arbitrary irreducible trinomial. This design effectively exploits Mastrovito approach and shifted polynomial basis (SPB) to reduce the time complexity and Karatsuba algorithm to reduce its space complexity. We show that this type of multiplier is only one $T_X$ slower than the fastest bit-parallel multiplier for all trinomials, where $T_X$ is the delay of one 2-input XOR gate. Meanwhile, its space complexity is roughly 3/4 of those multipliers. To the best of our knowledge, it is the first time that our scheme has reached such a time delay bound. This result outperforms previously proposed non-recursive Karatsuba multipliers.

Note: revised some errors

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Mastrovito multiplierKaratsubashifted polynomial basistrinomials
Contact author(s)
yunfeiyangli @ gmail com
History
2017-02-26: last of 4 revisions
2016-07-13: received
See all versions
Short URL
https://ia.cr/2016/694
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/694,
      author = {Yin Li and Xingpo Ma and Yu Zhang and Chuanda Qi},
      title = {Mastrovito Form of Non-recursive Karatsuba Multiplier for All Trinomials},
      howpublished = {Cryptology ePrint Archive, Paper 2016/694},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/694}},
      url = {https://eprint.iacr.org/2016/694}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.