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 P0, 1 (mod p_i) (where 3in) 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.