Prime number generation method, prime number generation apparatus, and cryptographic system

摘要

A prime number generation method for efficiently generating prime numbers that are highly resistant to the P-1 and P+1 methods. These prime numbers are used in a cryptosystem. Prime candidates are first generated, and the generated prime candidates are subjected to prime number judgment by either a probabilistic primality testing method or a deterministic primality testing method. A prime candidate P' is generated using odd random numbers, a judgment is made as to whether or not that prime candidate P' satisfies the expression P'≡0, �1 (mod p_i) (where 3<=i<=n) for prime numbers from p₃ to p_n (where p_n is the n'th prime). When that expression is satisfied, that prime candidate P' is excluded. Only those prime candidates P' that do not satisfy that condition are subjected to the prime number judgment.