International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jean-Claude Bajard
Laurent Imbert
Graham A. Jullien
Download:
URL: http://eprint.iacr.org/2004/279
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12245,
  title={Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic},
  booktitle={IACR Eprint archive},
  keywords={implementation / finite field arithmetic},
  url={http://eprint.iacr.org/2004/279},
  note={Submitted to ARITH17, the 17th IEEE symposium on computer arithmetic Laurent.Imbert@lirmm.fr 12852 received 28 Oct 2004, last revised 10 Mar 2005},
  author={Jean-Claude Bajard and Laurent Imbert and Graham A. Jullien},
  year=2004
}