Paper 2016/694

Mastrovito Form of Non-recursive Karatsuba Multiplier for All Trinomials

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


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

Available format(s)
Publication info
Preprint. MINOR revision.
Mastrovito multiplierKaratsubashifted polynomial basistrinomials
Contact author(s)
yunfeiyangli @ gmail com
2017-02-26: last of 4 revisions
2016-07-13: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.