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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/836}},
      url = {https://eprint.iacr.org/2017/836}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.