Patent ID: 8533243

Claim:
A representation converting apparatus for public key cryptography that converts data of a set of members represented by an affine representation representing a 2r-th degree algebraic torus T 2r (F q ) (r is a prime number, and q is an integer) to data of a set of members represented by a projective representation representing a quadratic algebraic torus T 2 (F q^r ), the apparatus comprising: an acquiring unit that acquires data of a set of members of the 2r-th degree algebraic torus T 2r (F q ) represented by the affine representation, the acquired set being (c 0 , c 1 , . . . , c r-2 ) (c i is a member of a finite field F q , where 0≦i≦r−2); a non-transitory memory that stores acquired data of the set; a multiplying unit that performs a multiplication operation on the acquired data of the set, the multiplication operation being determined by a condition under which the set of the quadratic algebraic torus T 2 (F q^r ) is included in the 2r-th degree algebraic torus T 2r (F q ), a modulus and a base of a quadratic extension, and a modulus and a base of an r-th degree extension; an adding/subtracting unit that performs an addition and subtraction operation determined by the condition, the moduli, and the bases, and therefore obtains data of a set of members of the quadratic algebraic torus T 2 (F q^r ) represented by the projective representation, the obtained data of the set being (a 0 , a 1 , . . . , a r-1 , b 0 , b 1 , . . . , b r-1 ) (a j is a member of F q and b j is a member of F q , where 0≦j≦r−1); and an output unit that outputs the obtained set, wherein x is a member added during a quadratic extension from an extension field F q^r to an extension field F q^2r , and the modulus of the quadratic extension is “f 2 (x)=x^2−δ” and the base of the quadratic extension is {1,x}, δ being a member of the finite field F q .