METHOD AND DEVICE FOR GENERATING PRIME NUMBERS, AND CRYPTOGRAPHIC SYSTEM

摘要

PROBLEM TO BE SOLVED: To provide a method of generating prime numbers used in a cryptosystem, and efficiently generating a prime number resistant to the P-1 method and the P+1 method. SOLUTION: Prime number candidates are generated (S1), and primality test is carried out on the generated prime number candidates by the stochastic primality test method or the definite primality test method. Prime numbers P' are generated using odd random numbers, and it is judged whether or not the prime number candidates P' satisfy the condition P'≡0,±1 (mod pi)(3<=i<=n) to the prime numbers from p3 up to pn (pn is n-th prime number), and if it is satisfied, the prime numbers P' are removed (S1). The primality test is carried out only on the prime number candidates P' which do not satisfy this condition (S3).