Prime number generation apparatus B-smoothness judgement apparatus and computer memory product

A prime number generation apparatus for generating a prime number larger than a predetermined prime number by using one or a plurality of prime numbers and a random number, comprising:

• means for generating a random number;
• means for obtaining a prime number candidate by using the generated random number and one or a plurality of prime numbers;
• means for judging as to whether or not the obtained prime number candidate is a prime number by using a provable prime number judging method;
• means for taking a measure to at least three polynomials F(p) which are prime factors of ps−1 (s:
• any arbitrary natural number which is set so that ps−1 has at least three prime factors) by a prime number p against prime factorization for obtaining p and q from n when n=pq (p and q are prime numbers);
• means for determining a maximum order of the polynomial F(p) to which a measure should be taken and means for giving a prime factor larger than a prescribed value to the polynomial F(p) whose order is not more than the determined order;
• wherein
• said means for determining includes means for determining the size of each prime number included in the polynomials F(p), according to computational complexity required for the prime factorization using the respective polynomials F(p) as for the polynomials F(p) to which a measure should be taken, and means for obtaining respective prime numbers according to the determined respective sizes,
• wherein when a prime number p of 1024 bits is to be generated, p−1, p+1, p2+p+1, p2+1 and p2−p+1 which are the polynomials F(p) to which a measure would be taken have prime factors of 515, 110, 109, 108 and 107 bits, respectively.

A prime number generation apparatus for generating a prime number p used for a secret key of an RSA cryptosystem, comprising:

• calculation means for calculating a prime number candidate by using one or a plurality of prime numbers and a random number;
• prime number judging means for judging as to whether or not the calculated prime number candidate is a prime number by using a provable prime number judging method;
• and
• strength judging means for judging the strength of the number judged as a prime number against iterated-encryption attack on RSA cryptosystem,
• wherein said strength judging means includes means for judging as to whether or not the following conditions are satisfied when numbers p and q judged as prime numbers are represented by p=2hpp1+1(hp<p1, p1:prime number) and q=2hqq1+1(hq<q1, q1:prime number):
• 1. p′1 and q′1 which satisfy p1=2p′1+1 and q1=2q′1+1 are prime numbers:
• 2. hp and hq are prime numbers;
• 3. as for xp, yp, xq, yq≧1
• prime numbers h′p and h′q which satisfy hp=2xp3yph′p+1,hq=2xq3yqhq′+1 exist;
• and
• 4. As for an encryption key e of RSA cryptosystem,
• gcd(e2x′3y′−1,(p−1)(q−1)/4)=1 holds;
• here,
• x′=max(xp,xq), y′=max(yp,yq).

A prime number generation apparatus comprising:

• means for taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of ps−1 (s:
• any arbitrary natural number which is set so that ps−1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;
• and
• means for determining the bit length of a prime number to be given to F(p) in view of a difference in the computational complexity required for the respective prime factorization methods, when the respective polynomials F(p) except for p−1 have prime factors of the same bit length.

A computer readable storage medium, storing a program to instruct a computer to perform:

• taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of ps−1 (s:
• any arbitrary natural number which is set so that ps−1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;
• and
• determining the bit length of a prime number to be given to F(p) in view of a difference in the computational complexity required for the respective prime factorization methods, when the respective polynomials F(p) except for p−1 have prime factors of the same bit length.

A method comprising:

• taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of ps−1 (s:
• any arbitrary natural number which is set so that ps−1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;
• determining the bit length of a prime number to be given to F(p) in view of a difference in the computational complexity required for the respective prime factorization methods, when the respective polynomials F(p) except for p−1 have prime factors of the same bit length;
• and
• using the determining in order to improve encryption security.

A prime number generation apparatus comprising:

• means for taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of ps−1 (s:
• any arbitrary natural number which is set so that ps−1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;
• said means including:
• a first means for calculating an evaluation value for probability that the prime factor of F(p) does not exceed a first prescribed value determined in advance, by carrying out a first step of calculating, from the equation v=(F(pmax)−F(pmin))*exp(−uln(u)), the number v of natural numbers included in a range having prime factors smaller than the first prescribed value in which pmax and pmin are the maximum value and the minimum value of p respectively, u=t*pb/log2 B holds and t is the order of the polynomial F(p), pb is the bit length of the prime number p to be generated and B is the first prescribed value, and by carrying out a second step of calculating v/(pmax−pmin) to obtain an evaluation value for probability;
• and
• a second means for taking a measure against F(p) whose obtained evaluation value for probability exceed a second prescribed value determined in advance.

A prime number generation method comprising:

• taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of ps−1 (s:
• any arbitrary natural number which is set so that ps−1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;
• said taking a measure including:
• calculating an evaluation value for probability that the prime factor of F(p) does not exceed a first prescribed value determined in advance, by carrying out a first step of calculating, from the equation v=(F(pmax)−F(pmin))*exp(−uln(u)), the number v of natural numbers included in a range having prime factors smaller than the first prescribed value in which pmax and pmin are the maximum value and the minimum value of p respectively, u=t*pb/log2 B holds and t is the order of the polynomial F(p), pb is the bit length of the prime number p to be generated and B is the first prescribed value, and by carrying out a second step of calculating v/(pmax−pmin) to obtain an evaluation value for probability;
• and
• taking a measure against F(p) whose obtained evaluation value for probability exceed a second prescribed value determined in advance.

A computer readable storage medium storing a program to perform a prime number generation method, said program performing:

• taking a measure to at least three polynomials F(p) against respective prime factorization methods for obtaining prime numbers p and q from a composite number n=pq, in which each polynomial F(p) indicated by a prime factor of ps−1 (s:
• any arbitrary natural number which is set so that ps−1 has at least three prime factors) is a product of prime numbers not larger than a prescribed number;
• said taking a measure including:
• calculating an evaluation value for probability that the prime factor of F(p) does not exceed a first prescribed value determined in advance, by carrying out a first step of calculating, from the equation v=(F(pmax)−F(pmin))*exp(−uln(u)), the number v of natural numbers included in a range having prime factors smaller than the first prescribed value in which pmax and pmin are the maximum value and the minimum value of p respectively, u=t*pb/log2 B holds and t is the order of the polynomial F(p), pb is the bit length of the prime number p to be generated and B is the first prescribed value, and by carrying out a second step of calculating v/(pmax−pmin) to obtain an evaluation value for probability;
• and
• taking a measure against F(p) whose obtained evaluation value for probability exceed a second prescribed value determined in advance.