New bit-parallel Montgomery multiplier for trinomials using squaring operation

• We construct a bit-parallel Montgomery multiplier over GF(2m)GF(2m) generated with all the irreducible trinomials using squaring operations.
• The space complexity of our proposal saves about m2/2m2/2 logic gates than any other Montgomery or Mastrovito multipliers for trinomials, and matches the Karatsuba multiplier.
• The time complexity of our proposal is slightly higher than the fastest multipliers, but no more than 2TX2TX.

A new bit-parallel Montgomery multiplier for GF(2m)GF(2m) is presented, where the field is generated with an irreducible trinomial. We first present a slightly generalized version of a newly proposed divide and conquer approach. Then, by combining this approach and a carefully chosen Montgomery factor, we can implement field multiplication using a composition of small polynomial multiplications and Montgomery squarings, which are simpler and more efficient. As a result, the proposed multiplier roughly saves m22 logic gates compared with the fastest multipliers, with time complexity as good as or better than previous Karatsuba-based multipliers for the same class of fields.