Blum Blum Shub Algorithm

Blum Blum Shub, often abbreviated B.B.S., is a pseudorandom number generator whose output is provably as hard to predict as solving a specific hard mathematical problem, which sets it apart from most pseudorandom generators used in practice, whose unpredictability is merely assumed rather than proven. It generates each new number in its sequence by squaring the previous number and reducing the result modulo a large composite number formed from two large prime factors chosen so the modulus satisfies particular technical conditions, and it derives its actual random output bits from either the parity or the least significant bits of each computed value; a distinctive further property is that any position in the sequence can be computed directly, without stepping through every earlier value, by using modular exponentiation together with Euler's theorem. Lenore Blum, Manuel Blum and Michael Shub proposed the generator in 1986, building on a one-way function described earlier by Michael Rabin.