# Blum Blum Shub

Template:More footnotes Template:Primary sources 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 − 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):

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

## Security

The generator is very slow. However, there is a proof reducing its securityTemplate:Clarify to the computational difficulty of computing modular square roots, a problem whose difficulty is equivalent to factoring. 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 factoring 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. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
General
• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }} available as PDF and Gzipped Postscript