Patent ID: 7634084

Claim:
A prime calculating apparatus for calculating a prime candidate N larger than a known prime q and testing primality of the calculated prime candidate N, comprising: a prime storage unit storing the known prime q; a management information storage unit storing unique management information; a random information generation unit operable to read the unique management information from the management information storage unit, and generate random information R based on the read unique management information; a candidate calculation unit operable to read the prime q from the prime storage unit, and calculate the prime candidate N using the read prime q and the generated random information R, according to N=2×random information R×prime q÷1; a primality testing unit operable to test primality of the calculated prime candidate N according to the Pocklington's primality test; and an output unit operable to output the calculated prime candidate N as a prime N when the primality of the calculated prime candidate N is determined, wherein said random information generation unit further includes: a reading subunit operable to read the unique management information from the management information storage unit; a random number calculation subunit operable to calculate a random number r; a combining subunit operable to make a combination of the read unique management information and the calculated random number r; and a computation subunit operable to compute the random information R based on the combination, and wherein the computation subunit computes the random information R by applying an injection function to the combination.