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

Abstract

In this paper, we present a low complexity bit-parallel Montgomery multiplier for $GF(2^{m})$ generated with irreducible Type C.1 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 multiplication 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.

Keywords

• Bit-parallel
• montgomery multiplication
• squaring
• type C.1 pentanomial