# 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

where *M* = *pq* is the product of two large primes *p* and *q*. At each step of the algorithm, some output is derived from *x*_{n+1}; the output is commonly either the bit parity of *x*_{n+1} or one or more of the least significant bits of *x*_{n+1}*.*

The seed *x*_{0} should be an integer that is co-prime to *M* (i.e. *p* and *q* are not factors of *x*_{0}) 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 *x*_{i} value directly (via Euler's Theorem):

where is the Carmichael function. (Here we have ).

## 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 *x _{n}* 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 , and (where is the seed). We can expect to get a large cycle length for those small numbers, because . The generator starts to evaluate by using and creates the sequence , , , = 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

- ↑ {{#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

## External links

- GMPBBS , a GPL'ed GMP-based implementation of Blum Blum Shub in C by Maria Morisot with implementations in Java and PHP also.
- An implementation in Java
- Randomness tests