Cryptology ePrint Archive: Report 2016/694
Mastrovito Form of Non-recursive Karatsuba Multiplier for All Trinomials
Yin Li and Xingpo Ma and 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.
Category / Keywords: Mastrovito multiplier, Karatsuba, shifted polynomial basis, trinomials
Date: received 12 Jul 2016, last revised 26 Feb 2017
Contact author: yunfeiyangli at gmail com
Available format(s): PDF | BibTeX Citation
Note: revised some errors
Version: 20170226:114632 (All versions of this report)
Short URL: ia.cr/2016/694
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]