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
-
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}
}
