Patent ID: 7043018

Claim:
A computer implemented prime number generation method for generating prime numbers used in a cryptosystem, comprising the steps of: generating a plurality of prime candidates P′ using odd random numbers; selecting prime candidates P′ for which neither P′+1 nor P′−1 is a multiple of 8 or 9, wherein the multiple of 8 or 9 is derived from a most resistant prime number in an index function, wherein the index function is defined by F(P′)=(P′−1)(P′+1); performing division operations on each of the selected prime candidates P′ with a subset of prime numbers selected from p 3 to p n (where p n is n′th prime); and subjecting prime candidates P′ to prime number judgment when, as a result of said division operations, following equation (D) holds true: P′≢ 0,±1( mod Pi ) ( D ) (where i is an integer such that 3≦i≦n).