Caution
This BBS generator is deprecated. It’s better to use SecureRNG instead, which provides hardware-based cryptographically secure random numbers.
A PRNG is said to be cryptographically secure if there is no polynomial-time algorithm which, on input of the first l bits of the output sequence, can predict the (l+1)st bit of the sequence with probability significantly greater than 0.5. This is equivalent to saying there exists no polynomial-time algorithm that can correctly distinguish between an output sequence from the PRNG and a truly random sequence of the same length with probability significantly greater than 0.5 [Menezes].
The Blum-Blum-Shub pseudo-random number generator is cryptographically-secure under the assumption that the quadratic residuosity problem is intractable. The algorithm consists of the following:
Generate two large and distinct primes, p and q, each congruent to 3 mod 4. Define m = pq.
Select a seed s taking a value between 1 and m-1, such that the greatest common divisor between s and m is 1. Let \(x_0 = s^2\ mod \ m\). For \(I = 1, 2,\dotsc`\) generate:
where \(v \ge 1\).
The bit-sequence \(z_1, z_2, z_3,\dotsc\) is then the output sequence used.