| 摘要 |
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 b eing 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 , a k (k=1, 2, ...,m) is an integer which satisfies congruence equation a k(P1P2~~ ~ P m/P k)=1 (mod P k), while B k represents {A mod (P k-1 + 1. An adder 107 outputs the integer X as an integer with a predetermined number of bits.
|
