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 comprises: an elliptic curve generating unit 210 that searches an elliptic curve that satisfies a speeding-up condition that reduces calculation quantity of arithmetic on the elliptic curve among a group of isogenous elliptic curves of degree L.sub.1 that is a group of elliptic curves that has the same order as and a certain relationship with the first elliptic curve; an elliptic curve condition judgment unit 220 that judges whether the elliptic curve that satisfies the speeding-up condition is searched or not by the elliptic curve generating unit 210; and an elliptic curve output unit 230 that outputs an elliptic curve in the case that the elliptic curve condition judgment unit 220 judges that the elliptic curve that satisfies the speeding-up condition is searched.