## 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

Short URL: ia.cr/2016/694

[ Cryptology ePrint archive ]