Patent ID: 7539719

Claim:
A method of performing multiplication through d-bit parallel processing using a serial multiplier by obtaining C=(c 0 , . . . , c n−1 ) of a product of two elements A and B of a finite field GF(2 n ) when a defining polynomial f(x) of degree n in the finite field GF(2 n ) is defined by f ( x )= x n +h ( x )= x n +( f n−1 x n−1 + . . . +f 1 x+f 0 ), f i ∈{0,1} , where f n−1 = . . . =f n−d+1 =0, d≧2, d is an integer, α is a root of the defining polynomial, A and B of the finite field are expressed as A=α 0 +α 1 α+α 2 α 2 + . . . +α n−1 α n−1 =(α 0 ,α 1 ,α 2 , . . . ,α n−1 ), B=b 0 +b 1 α+b 2 α 2 + . . . +b n−1 α n−1 =( b 0 ,b 1 ,b 2 , . . . ,b n−1 ) with respect to the root α, and C of the product of A and B can be rewritten as C=A×B mod f(α), the method comprising: permuting the last d coefficients (a n−1 , . . . , a n−d ) of a multiplier, which is A, with predetermined variables (s n−1 , . . . , s n−d ); operating C:=C⊕(b i+j ●A) for (i+j) th coefficient of a multiplicand, which is B, to update coefficients of C, where i and j are integers, and A :=( s n−1−j ,α 0 , . . . ,α n−2 )⊕(0, s n−1−j ●f 1 , . . . ,s n−1−j ●f n−d ,0, . . . ,0) repeatedly for j=0 to (d−1) to update coefficients of A, where ⊕ represents an XOR operation and ● represents an AND operation; and repeatedly performing the permuting and operating by increasing i from 0 to (n−1) by d to obtain a final product C.