|
Published Articles >> Table of Contents >> Abstract
17th IEEE Symposium on Computer Arithmetic (ARITH'05)
pp. 164-171
Parallel Montgomery Multiplication in GF (2^k) Using Trinomial Residue Arithmetic
Jean-Claude Bajard, LIRMM, CNRS UMR
Laurent Imbert, LIRMM, CNRS UMR and University of Calgary
Graham A. Jullien, University of Calgary
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.2005.34
Send link to a friend
| Abstract |
|
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.
|
 Additional Information
|
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
|
|
