Cryptology ePrint Archive: Report 2017/836

Efficient Square-based Montgomery Multiplier for All Type C.1 Pentanomials

Yin Li and Xingpo Ma and Qin Chen and Chuanda Qi

Abstract: In this paper, we present a low complexity bit-parallel Montgomery multiplier for $GF(2^m)$ generated with a special class of irreducible pentanomials $x^m+x^{m-1}+x^k+x+1$. Based on a combination of generalized polynomial basis (GPB) squarer and a newly proposed square-based divide and conquer approach, we can partition field multiplications into a composition of sub-polynomial multiplications and Montgomery/GPB squarings, which have simpler architecture and thus can be implemented efficiently. Consequently, the proposed multiplier roughly saves 1/4 logic gates compared with the fastest multipliers, while the time complexity matches previous multipliers using divide and conquer algorithms.

Category / Keywords: Montgomery multiplication and Squaring and Bit-parallel and Type C.1 Pentanomial

Date: received 30 Aug 2017, last revised 2 Sep 2017

Contact author: yunfeiyangli at gmail com

Available format(s): PDF | BibTeX Citation

Note: Revised some grammar errors

Version: 20170902:121940 (All versions of this report)

Short URL: ia.cr/2017/836

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]