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

*Jean-Claude Bajard and 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.

**Category / Keywords: **implementation / finite field arithmetic

**Publication Info: **Submitted to ARITH17, the 17th IEEE symposium on computer arithmetic

**Date: **received 28 Oct 2004, last revised 10 Mar 2005

**Contact author: **Laurent Imbert at lirmm fr

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20050310:223709 (All versions of this report)

**Short URL: **ia.cr/2004/279

[ Cryptology ePrint archive ]