Patent ID: 7346641

Claim:
A method of converting a standard representation to a dual representation in a finite field GF(2 n ), in which a standard basis represented coefficient vector B=(b 0 , b 1 , b 2 , . . . , b n−1 ) of an element B of the finite field GF(2 n ) is converted to a dual basis represented coefficient vector B′=(b′ 0 , b′ 1 , b′ 2 , . . . , b′ n−1 ) using a defining polynomial x n +x k(3) +x k(2) +x k(1) +1, the method being performed by an apparatus for basis conversion, the apparatus including a n-bit token register to store each row vector in a basis conversion matrix, a n-bit data register to store a vector to be converted, n bit multipliers performing bit-by-bit multiplications between the outputs of the token register and the outputs of the data registers, an adder connected to the bit multipliers to add the results of the bit-by-bit multiplications and a controller to control the token register to output the row vectors, the method comprising: the controller receiving the exponents n, k(3), k(2), and k(1) of the defining polynomial x n +x k(3) +x k(2) +x k(1) +1; the data register storing B=(b 0 , b 1 , b 2 , . . . , b n−1 ); the controller reading (b k(1) , b k(1)−1 , b k(1)−2 , . . . , b 0 ) from the data register and obtaining 0-th through k(1)-th components of B′ by performing a vector operation (b′ 0 , b′ 1 , b′ 2 , . . . , b′ k(1) )=(b 0 +b k(1) , b k(1)−1 , b k(1)−2 , . . . , b 0 ) through the bit multipliers and adder, The controller reading (b n−1 , b n−2 , . . . , b k(3) ) from the data register and obtaining (k(1)+1)-th through (k(1)+n−k(3))-th components of the dual basis represented coefficient vector B′ by performing a vector operation (b′ k(1)+1 , b′ k(1)+2 , . . . , b′ k(1)+n−k(3) )=(b n−1 , b n−2 , . . . , b k(3) ) through the bit multipliers and adder; the controller reading (b k(3)−1 , . . . , b k(2) ) and (b n−1 , . . . , b n−k(3)+k(2) ) from the data register and obtaining (k(1)+1+n−k(3))-th through (k(1)+n−k(2))-th components of B′ by performing a vector operation (b′ k(1)+1+n−k(3) , b′ k(1)+2+n−k(3) , . . . , b′ k(1)+n−k(2) )=(b k(3)−1 +b n−1 , b k(3)−2 +b n−2 , . . . , b k(2) +b n−k(3)+(2) ); and the controller reading b k(2)−1 , b k(2)−2 , . . . , b k(1)+1 , b n−1−k(3)+k(2) ), b n−2−k(3)+k(2) , . . . , b n+1−k(3)+k(1) ) and (b n−1 , b n−2 , . . . , b n+1−k(2)+k(1) ) from the data register and obtaining (k(1)+1+n−k(2))-th through (n−1)-th components of B′ by performing a vector operation (b′ k(1)+1+n−k(2) , b′ k(1)+2+n−k(2) , . . . , b′ n−1 )=b k(2)−2 +b n−2−k(3)+k(2) +b n−2 , . . . , b k(1)+1 +b n+1−k(3)+k(1) +b n+1−k(2)+k(1) )through the bit multipliers and adder.