Parameter generation device, parameter generation method and computer readable medium

A parameter generation method to be used by a parameter generation device to generate a seed being a parameter to determine an elliptic curve used for paring computation, the parameter generation method comprising:

• calculating, as a composite number condition, a condition of an integer under which at least either of a first integer and a second integer obtained by substituting an integer into each of a first polynomial and a second polynomial that constitute an elliptic curve family from which the elliptic curve is selected is a composite number;
• searching for an integer whereof a Hamming weight in a signed binary representation represented in a non-adjacent form is included in a weight range defined beforehand, deleting an integer that satisfies the composite number condition from a set of integers obtained by search, and regarding a set of remaining integers obtained by deleting the integer that satisfies the composite number condition as a set of seed candidates;
• and
• deciding whether both of the first polynomial and the second polynomial become prime numbers when each integer of the set of seed candidates is substituted into the first polynomial and the second polynomial, and extracting an integer for which both of the first polynomial and the second polynomial become prime numbers, from the set of seed candidates, as the seed.

A non-transitory computer readable medium storing a parameter generation program to be used by a parameter generation device to generate a seed being a parameter to determine an elliptic curve used for paring computation, the parameter generation program causing a computer to perform:

• a preliminary calculation process to calculate, as a composite number condition, a condition of an integer under which at least either of a first integer and a second integer obtained by substituting an integer into each of a first polynomial and a second polynomial that constitute an elliptic curve family from which the elliptic curve is selected is a composite number;
• a seed candidate generation process to search for an integer whereof a Hamming weight in a signed binary representation represented in a non-adjacent form is included in a weight range defined beforehand, to delete an integer that satisfies the composite number condition from a set of integers obtained by search, and to regard a set of remaining integers obtained by deleting the integer that satisfies the composite number condition as a set of seed candidates;
• and
• a prime number decision process to decide whether both of the first polynomial and the second polynomial become prime numbers when each integer of the set of seed candidates is substituted into the first polynomial and the second polynomial, and to extract an integer for which both of the first polynomial and the second polynomial become prime numbers, from the set of seed candidates, as the seed.