Secure parameter generating device and parameter generating method in algebraic curve crytography

A secure parameter generating method in an algebraic curve cryptography having the definitions expression of αYa+βXb+1=0, comprising the steps of:

• a Stickelberger element computing procedure for computing a Stickelberger element ω in an ab cyclotomic, respectively based on two different prime numbers a and b specifying degree of complexity of curve;
• a Jacobian addition candidate value computing, procedure for computing Jacobian addition candidate value j corresponding to the two different prime numbers a and b, and a prime number p corresponding to the Jacobian addition candidate value j, respectively based on the prime number a, the prime number b, the size n of an encryption key, and the Stickelberger element ω;
• an order candidate value computing procedure for computing a class H consisting of a plurality of candidate values for order of a Jacobian group of an algebraic curve specified by the prime number a and the prime number b, respectively based on the prime number a, the prime number b, and the Jacobian addition candidate value j;
• a security judging procedure for searching for a candidate value h meeting a security condition such as almost prime number characteristic from the class H, according to the class H;
• and
• a parameter deciding procedure for computing a parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a, the prime number b, and the prime number p, respectively based on the prime number a, the prime number b the prime number p, and the, candidate value h;
• and
• supplying said parameter to an algebraic curve cryptographic public key system.

A computer readable memory storing a program for generating a secure parameter in an algebraic curve cryptography having the definition expression of αYa+βXb+1=0, which, when executing on a computer causes the computer to carry out the steps comprising:

• a Stickelberger element computing procedure for computing a Stickelberger element co in an ab cyclotomic, respectively based on two different prime numbers a and b specifying degree of complexity of curve;
• a Jacobian addition candidate value computing procedure for computing Jacobian addition candidate value j corresponding to the two different prime numbers a and b, and a prime number p corresponding to the Jacobian addition candidate value j, respectively based on the prime number a, the prime number b, the size n of an encryption key, and the Stickelberger element ω;
• an order candidate value computing procedure for computing a class H consisting of a plurality of candidate values for order of a Jacobian group of an algebraic curve specified by the prime number a and the prime number b, respectively based on the prime number a, the prime number b, and the Jacobian addition candidate value j;
• a security judging procedure for searching for a candidate value h meeting a security condition such as almost prime number characteristic from the class H, according to the class H;
• and
• a parameter deciding procedure for computing a parameter of an algebraic curve whose order of the Jacobian group is in accord with the candidate value h, of the algebraic curves specified by the prime number a, the prime number b, and the prime number p, respectively based on the prime number a, the prime number b, the prime number p, and the candidate value h.