| 摘要 |
<p>A generator 101 produces randomly an integer A, which satisfies 0</= A<(P1-1)(P2-1)...(Pm-1), in synchronism with a clock pulse applied via an input terminal 180, where each of P1, P2, ...Pm is a prime number equal to or more than 2. First calculating means 4 calculates an integer X, whose probability of being a prime number is high, using the integer A based on equation X= a1(P1P2...Pm/P1)B1 + a2(P1P2...Pm/P2)B2 + ... + am(P1P2...Pm/Pm)Bm(mod P1P2...Pm). In this case, ak (k=1, 2, ..., m) is an integer which satisfies congruence equation ak(P1P2... Pm/Pk)=1 (mod Pk), while Bk represents äA mod (Pk-1)ü + 1. An adder 107 outputs the integer X as an integer with a predetermined number of bits. <IMAGE></p> |
