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

Yin Li; Xingpo Ma; Qin Chen; Chuanda Qi

Paper 2017/836

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

Yin Li, Xingpo Ma, 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.

Note: Revised some grammar errors

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Contact author(s): yunfeiyangli @ gmail com
History: 2017-09-02: last of 3 revisions; 2017-08-31: received; See all versions
Short URL: https://ia.cr/2017/836
License: CC BY

BibTeX

@misc{cryptoeprint:2017/836,
      author = {Yin Li and Xingpo Ma and Qin Chen and Chuanda Qi},
      title = {Efficient Square-based Montgomery Multiplier for All Type C.1 Pentanomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/836},
      year = {2017},
      url = {https://eprint.iacr.org/2017/836}
}