Patent ID: 8782114

Claim:
An arithmetic device for performing algebraic torus operation to which either one of a set of n elements (h 0 , h 1 , . . . , h n−1 ) (h i : a member of a finite field F p^m , 0≦i≦n−1) representing a member g of an n-th degree algebraic torus T n (F p^m ) (n: positive integer, p: prime number, m: positive integer) in a projective representation and a set of φ(n) elements (c 0 , c 1 , . . . , c φ(n)−1 ) (c i : a member of the finite field F p^m , 0≦i≦φ(n)−1, φ(x): Euler function) represented by an affine representation is input, the arithmetic device comprising: a representation converting unit configured to convert either one of the set of n elements (h 0 , h 1 , . . . , h n−1 ) and the set of φ(n) elements (c 0 , c 1 , . . . , c φ(n)−1 ) into a set of n elements (h′ 0 , h′ 1 , . . . , h′ n−1 ) (h′ i : a member of the finite field F p^m , 0≦i≦n−1) in which at least one element is a zero element “0” or an identity element “1” out of n elements representing the member g of the n-th degree algebraic torus T n (F p^m ) in a limited projective representation; and an arithmetic unit configured to omit part of F p^m operation that is arithmetic operation in a finite field F p^mn based on a fact that an element in the set of n elements (h′ 0 , h′ 1 , . . . , h′ n−1 ) represented by the limited projective representation is a zero element “0” or an identity element “1” when performing the F p^mn operation in combination with the F p^m operation.