Patent ID: 6957243

Claim:
A circuit for performing multiplication of two elements from a finite Galois field GF(2 k ) wherein said elements are represented by polynomials a(x) and b(x) and multiplication is carried out modulo an irreducible polynomial p(x) of degree k, said circuit comprising: a first multiplier modulo p(x) for A j (x) with (T−1)≧j≧0 and b(x), where A j (x) is a polynomial of degree n−1 of the form ∑ i = 0 n - 1 ⁢ ⁢ a jn + i ⁢ x i where α jn+i is the coefficient for the x jn+i term in the polynomial a(x) and wherein k=nT; a summer receiving the output from said multiplier; a storage means for holding the output from said summer for each of T cycles of operation of said circuit; a second multiplier modulo p(x) for multiplying the current contents of said storage means by x n , the output of said second multiplier also being supplied as an input to said summer.