PRIME FORMING MEANS, B-SMOOTH CHARACTERISTIC DECIDING APPARATUS AND RECORDING MEDIUM

摘要

PROBLEM TO BE SOLVED: To provide a prime forming apparatus capable of forming a deterministic prime, is capable of making adequate remedy for a prime factoring method and is capable of forming the prime strong to a repetitive ciphering attack when used for a secret key of an RSA cipher. SOLUTION: A larger prime candidate is calculated by using the one or plural primes Pi formed by a prime forming device 2 and the random numbers generated by a random number generator 4. Whether the prime candidate is a prime or not is decided by using a deterministic element deciding method in a deterministic prime deciding device 6. When the candidate is decided to be the prime, the prime (p) is outputted. The remedy for the prime factoring method is executed with reset to at least three pieces of polynomials which are the factors of p'-1 ((s): arbitrary natural number) by the prime (p). When the prime (p) is used for the secret key of the RSA cipher, the prime (p) strong to the repetitive ciphering attack is formed for the RSA cipher.