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
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