Patent ID: 7209555

Claim:
An elliptic curve converting device that converts a first elliptic curve defined on a finite field F into a second elliptic curve defined on the finite field F, the elliptic curve converting device comprising: a search unit operable to search for an elliptic curve that satisfies a speeding-up condition that reduces a calculation quantity of arithmetic on the elliptic curve from among a group of isogenous elliptic curves of degree L 1 , the group of isogenous elliptic curves of degree L 1 being a group of elliptic curves having the same order as the first elliptic curve and a relationship with the first elliptic curve; a judgment unit operable to judge whether or not an elliptic curve that satisfies the speeding-up condition was searched by the search unit; and an output unit operable to output, if the judgment unit judges that an elliptic curve that satisfies the speeding-up condition was searched by the search unit, the elliptic curve judged by the judgment unit as satisfying the speeding-up condition as the second elliptic curve.