Patent ID: 7539719
Filing Date: 2009-05-26
Classification: G06F

Abstract:
1. 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 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 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 operating C:=C⊕(b 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.