Patent Document ID: 20040098437
Application ID: 10702740
Patent Flag: 0

Claim One:
1. 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&equals;(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′&equals;(b′ 0, b′ 1, b′ 2,..., b′ n−1 ) using a defining polynomial x n &plus;x k(3) &plus;x k(2) &plus;x k(1) &plus;1, the method being performed by an apparatus for basis conversion, the apparatus including a token register composed of “n” bits to store each row vector in a basis conversion matrix, a data register composed of “n” bits to store a vector to be converted, “n” number of bit multipliers performing bit-by-bit multiplications between the outputs of the token register and the outputs of the data registers, and an adder connected to the output terminals of the bit multipliers to add the results of the bit-by-bit multiplications, the method comprising: inputting the exponents n, k(3), k(2), and k(1) of the defining polynomial x n &plus;x k(3) &plus;x k(2) &plus;x k(1) &plus;1; storing the standard basis represented coefficient vector B&equals;(b 0, b 1, b 2,..., b n−1 ) to be converted in the data register; obtaining 0-th through k(1)-th components of the dual basis represented coefficient vector B′ using a vector formula (b′ 0, b′ 1, b′ 2,..., b′ k(1) )&equals;(b 0 &plus;b k(1), b k(1) −1, b k(1)−2,..., b 0 ); obtaining (k(1)&plus;1)-th through (k(1)&plus;n−k(3))-th components of the dual basis represented coefficient vector B′ using a vector formula (b′ k(1)&plus;1, b′ k( 1)&plus;2,..., b′ k(1)&plus;n−k(3) )&equals;(b n−1, b n−2,..., b k(3) ); obtaining (k(1)&plus;1&plus;n−k(3))-th through (k(1)&plus;n−k(2))-th components of the dual basis represented coefficient vector B′ using a vector formula (b′ k(1)&plus;1&plus;n−k(3), b′ k(1)&plus;2&plus;n−k(3),..., b′ k(1)&plus;n−k(2) )&equals;(b k(3)−1 &plus;b n&equals;1, b k(3)−2 &plus;b n−2,..., b k(2) &plus;b n−k(3)&plus;k(2) ); and obtaining (k(1)&plus;1&plus;n−k(2))-th through (n−1)-th components of the dual basis represented coefficient vector B′ using a vector formula (b′ k(1)&plus;1&plus;n−k(2 ), b′ k(1)&plus;2&plus;n−k(2),..., b′ n−1 )&equals;(b k(2)−1 &plus;b n−1−k(3)&plus;k(2) &plus;b n−1, b k(2)−2 &plus;b n−2−k(3)&plus;k(2) &plus;b n−2,..., b k(1)&plus;1 &plus;b n&plus;1−k(3)&plus;k(1) &plus;b n&plus;1−k(2)&plus;k(1) ).