loading...
Parallel Montgomery Multiplication in GF (2^k) Using Trinomial Residue Arithmetic
Cape Cod, Massachusetts, USA June 27-June 29
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.2005.3417th IEEE Symposium on Computer Arith ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.