Pseudo-random number generating method and apparatus therefor

Abstract From the Canadian patent

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 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.