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
-
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},
url = {https://eprint.iacr.org/2016/694}
}
