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.