Encyclopedia > Blum Blum Shub

  Article Content

Blum Blum Shub

Blum Blum Shub (BBS) is a pseudorandom number generator, of the form:

xn+1 = (xn)2 mod M

where M is the product of two large primes, and the output is the least significant bit of xn, or the parity of xn. Or, the output can be several of the least significant bits of xn.

The generator is not appropriate for use in simulations, only for cryptography, because it is not very fast. However, it has an unusually strong security proof, which relates the quality of the generator to the difficulty of integer factorization. When the primes are chosen appropriately, and O(log log M) bits of each xn are output, then in the limit as M grows large, distinguishing the output bits from random will be at least as difficult as factoring M.

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).

If integer factorization is difficult (as is widely suspected) then BBS with large M will have an output free from any nonrandom patterns that can be discovered with any reasonable amount of calculation. There are very few random number generators or cryptographic systems with such strong results known. However, it's theoretically possible that a fast algorithm for factoring will someday be found, so BBS is not yet guaranteed to be secure.

BBS was originally proposed in:

L. Blum, M. Blum, and M. Shub.
A Simple Unpredictable Pseudo-Random Number Generator.
SIAM Journal on Computing, volume 15, pages 364-383, May 1986



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Northampton, Suffolk County, New York

... 9.8% who are 65 years of age or older. The median age is 34 years. For every 100 females there are 91.0 males. For every 100 females age 18 and over, there are 82.9 ...

 
 
 
This page was created in 34.8 ms