# Blum Blum Shub

(Redirected from Blum blum shub)

Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub[1] that is derived from Michael O. Rabin's oblivious transfer mapping.

Blum Blum Shub takes the form

${\displaystyle x_{n+1}=x_{n}^{2}{\bmod {M}}}$,

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+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.

The seed x0 should be an integer that is co-prime to M (i.e. p and q are not factors of x0) and not 1 or 0.

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), φ(q)) 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):

${\displaystyle x_{i}=\left(x_{0}^{2^{i}{\bmod {\lambda }}(M)}\right){\bmod {M}}}$,

where ${\displaystyle \lambda }$ is the Carmichael function. (Here we have ${\displaystyle \lambda (M)=\lambda (p\cdot q)=\operatorname {lcm} (p-1,q-1)}$).

## Security

There is a proof reducing its security to the computational difficulty of solving the quadratic residuosity problem.[1] When the primes are chosen appropriately, and O(log log M) lower-order bits of each xn are output, then in the limit as M grows large, distinguishing the output bits from random should be at least as difficult as solving the Quadratic residuosity problem modulo M.

## Example

Let ${\displaystyle p=11}$, ${\displaystyle q=19}$ and ${\displaystyle s=3}$ (where ${\displaystyle s}$ is the seed). We can expect to get a large cycle length for those small numbers, because ${\displaystyle {\rm {gcd}}(\varphi (p-1),\varphi (q-1))=2}$. The generator starts to evaluate ${\displaystyle x_{0}}$ by using ${\displaystyle x_{-1}=s}$ and creates the sequence ${\displaystyle x_{0}}$, ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$, ${\displaystyle \ldots }$ ${\displaystyle x_{5}}$ = 9, 81, 82, 36, 42, 92. The following table shows the output (in bits) for the different bit selection methods used to determine the output.

Even parity bit Odd parity bit Least significant bit
0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0

## References

1. ^ a b Blum, Lenore; Blum, Manuel; Shub, Mike (1 May 1986). "A Simple Unpredictable Pseudo-Random Number Generator". SIAM Journal on Computing. 15 (2): 364–383. doi:10.1137/0215025.
General