IACR paper details
Title  Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic 

Booktitle  IACR Eprint archive 

Pages  

Year  2004 

URL  http://eprint.iacr.org/2004/279 

Author  JeanClaude Bajard 

Author  Laurent Imbert 

Author  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 $k1$, 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.


Search for the paper
@misc{eprint200412245,
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={JeanClaude Bajard and Laurent Imbert and Graham A. Jullien},
year=2004
}
Download a complete BibTeX file.