Blum Blum Shub

BlumBlumShub refers to a cryptographically strong PseudoRandomNumberGenerator designed by Lenore Blum, Manuel Blum and Michael Shub.

The sequence is:

X(n+1) = X(n)^2 mod M

Where M is the product of two large primes P and Q, both congruent to 3 mod 4.

Only the lowest order bits of X should be used, however, in general, the lowest log log M bits.

Also, to ensure a long period, gcd(phi(P-1), phi(Q-1)) should be as small as possible.

BlumBlumShub is suitable for any cryptographic application, because it has been proven that breaking the generator is at least as hard as factoring M. It is, however, really, really slow.