PRIME NUMBER GENERATION PROGRAM, RECORDING MEDIUM WITH THE PROGRAM RECORDED THEREON, PRIME NUMBER GENERATION DEVICE AND PRIME NUMBER GENERATION METHOD

摘要

PROBLEM TO BE SOLVED: To efficiently generate a prime number other than power-of-2 length by using a deterministic prime number judgment (generation) method.;SOLUTION: Designation of the bit length of a desired prime number P_n is received and, according to the bit length of the prime number P_n whose designation is received, each bit length of the prime numbers {P₁, ..., P_n-1} is calculated in advance. Then, on the basis of each bit length of the calculated prime numbers {P₁, ..., P_n-1} and by using a prime number P_i(1≤i≤n-1) and a random number r_i, a prime number P_i+1 whose bit length is longer than that of the prime number P_i and whose value is larger than that of the prime number P_i is successively generated. Thus, the desired prime number P_n can be eventually generated.;COPYRIGHT: (C)2008,JPO&INPIT