loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
17th IEEE Symposium on Computer Arithmetic (ARITH'05)
Parallel Montgomery Multiplication in GF (2^k) Using Trinomial Residue Arithmetic
Cape Cod, Massachusetts, USA
June 27-June 29
ISBN: 0-7695-2366-8
Jean-Claude Bajard, LIRMM, CNRS UMR
Laurent Imbert, LIRMM, CNRS UMR and University of Calgary
Graham A. Jullien, University of Calgary
We propose the first general multiplication algorithm in GF(2^k) with a subquadratic area complexity of 0(k^8/5) = 0(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 n pairwise prime trinomials, T₁, …, T_n, of degree d such that nd ≥ k. Our algorithm is based on Montgomery's multiplication applied to the ring formed by the direct product of the trinomials.
Citation:
Jean-Claude Bajard, Laurent Imbert, Graham A. Jullien, "Parallel Montgomery Multiplication in GF (2^k) Using Trinomial Residue Arithmetic," arith, pp.164-171, 17th IEEE Symposium on Computer Arithmetic (ARITH'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.