Saturday, June 12, 2004


Wikipedia has a pretty decent entry on the Blum-Blum-Shub pseudorandom number generation algorithm. Why should anyone care about this, you ask?

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.


If integer factorization is difficult (as is 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.
That's why.


Post a Comment

<< Home