Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al., 1986).
Blum Blum Shub takes the form:
where M=pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from xn; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.
The two primes, p and q, should both be congruent to...
more
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al., 1986).
Blum Blum Shub takes the form:
where M=pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from xn; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.
The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue) and gcd(φ(p-1), φ(q-1)) should be small (this makes the cycle length large).
An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly (via Euler's Theorem):
The generator is not appropriate for use in simulations, only for cryptography, because it is very slow. However, it has an unusually strong security proof, which relates the quality of the generator to the computational...
less
