Paper 2004/279

Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic

Jean-Claude Bajard, Laurent Imbert, and Graham A. Jullien

Abstract

We propose the first general multiplication algorithm in $\mathrm{GF}(2^k)$ with a subquadratic area complexity of $\mathcal{O}(k^{8/5}) = \mathcal{O}(k^{1.6})$. Using the Chinese Remainder Theorem, we represent the elements of $\mathrm{GF}(2^k)$; i.e. the polynomials in $\mathrm{GF}(2)[X]$ of degree at most $k-1$, by their remainder modulo a set of $n$ pairwise prime trinomials, $T_1,\dots,T_{n}$, of degree $d$ and such that $nd \geq k$. Our algorithm is based on Montgomery's multiplication applied to the ring formed by the direct product of the trinomials.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Submitted to ARITH17, the 17th IEEE symposium on computer arithmetic
Keywords
finite field arithmetic
Contact author(s)
Laurent Imbert @ lirmm fr
History
2005-03-10: last of 4 revisions
2004-10-30: received
See all versions
Short URL
https://ia.cr/2004/279
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/279,
      author = {Jean-Claude Bajard and Laurent Imbert and Graham A.  Jullien},
      title = {Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic},
      howpublished = {Cryptology ePrint Archive, Paper 2004/279},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/279}},
      url = {https://eprint.iacr.org/2004/279}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.