Parallel Multiplication in GF(2k) using Polynomial Residue Arithmetic

We present a novel method of parallelization of the multiplication operation in GF(2^k) for an arbitrary value of k and arbitrary irreducible polynomial n(x) generating the field. The parallel algorithm is based on polynomial residue arithmetic, and requires that we find L pairwise relatively prime modulim _i(x) such that the degree of the product polynomialM(x)=m ₁(x)m ₂(x)··· m_L(x) is at least 2k. The parallel algorithm receives the residue representations of the input operands (elements of the field) and produces the result in its residue form, however, it is guaranteed that the degree of this polynomial is less than k and it is properly reduced by the generating polynomial n(x), i.e., it is an element of the field. In order to perform the reductions, we also describe a new table lookup based polynomial reduction method.