Patent ID: 7130422

Claim:
An information security device that handles predetermined information securely and reliably based on an intractability of factorization, by generating two primes and using a multiplication of the two primes, said device comprising: an acquiring unit operable to acquire a known prime q and n number of known primes L 1 , L 2 , . . . , L n , where L 1 , L 2 , . . . , L n are primes, other than 2, that are smaller than the prime q, and the prime q satisfies q=1 mod L i (i=1, 2, . . . , n); a generating unit operable to generate a number N whose bit length is twice as large as a bit length of the prime q, where numbers that relate to any of the primes L 1 , L 2 , . . . , L n are excluded from the generation of the number N; and a judging unit operable to judge primality of the number N, and output the number N as a prime if the number N is judged as being prime, wherein the generating unit is operable to generate the number N that satisfies N=1 mod L i (i=1, 2, . . . , n), and wherein the generating unit includes: a random number generating unit operable to generate a random number R′ whose bit length is (Lenq−LenL−1), where Lenq is the bit length of the prime q and LenL is a bit length of (L 1 ×L 2 × . . . ×L n ); and a judgement target generating unit operable to (a) generate a number R R=L 1 ×L 2 × . . . ×L n ×R′ using the random number R′ and the primes L 1 , L 2 , . . . , L n , and (b) generate the number N N =2 ×R×q+ 1 using the prime q and the number R, and wherein the judging unit judges the primality of the number N, using the number N and the number R generated by the judgement target generating unit.