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

Jean-Claude Bajard; Laurent Imbert; Graham A.  Jullien

Paper 2004/279

Parallel Montgomery Multiplication in $G F (2^{k})$ using Trinomial Residue Arithmetic

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

Abstract

We propose the first general multiplication algorithm in $GF (2^{k})$ with a subquadratic area complexity of $O (k^{8 / 5}) = O (k^{1.6})$ . Using the Chinese Remainder Theorem, we represent the elements of $GF (2^{k})$ ; i.e. the polynomials in $GF (2) [X]$ of degree at most $k - 1$ , by their remainder modulo a set of pairwise prime trinomials, , of degree and such that . 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: 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},
      url = {https://eprint.iacr.org/2004/279}
}

Paper 2004/279

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

Abstract

Metadata

Parallel Montgomery Multiplication in $G F (2^{k})$ using Trinomial Residue Arithmetic