** Next:** Statistical Tests
** Up:** Random Number Generators
** Previous:** TT800 and Mersenne Twister

##

Blum Blum Shub Generator

As shown in [2] and [4], LCGs are vulnerable to attacks
if they are used to generate keys in a cryptosystem or in similar situations
because it is possible to recover the parameters of LCGs in polynomial time
given several observed outputs.
Unlike all RNGs mentioned above, this generator has very strong
cryptographic properties such as PT unpredictable (see Section
2.2) based on the unproven assumption
that PNP in computational complexity theory.
Proposed in [3], BBS is a random bit generator with the following
simple form

where is the product of two large distinct primes, and the output
is the least significant bit of or the parity of . The
main difficulty of predicting
BBS's output lies in the intractability of ``quadratic residuosity'' problem
, which is: Given a composite number , find whether is a perfect
square modulo . It has been proven that this is as hard
as cracking the RSA public-key cryptosystem which involves
the factoring of a large composite.
However, BBS is not a permutation generator as the RNGs mentioned above. A
-permutation generator is a program which produces permutations of
a set of distinct objects. Each of these permutations is called a
-permutation. A full-period RNG with period length is also an
-permutation generator since any consecutive outputs form an
-permutation. The period length of BBS is much lesses than , therefore,
it can not be adapted to produce uniform random variates between 1 and .
For example, use use , and hence the period is much lesser than 16873.
Due to this reason, BBS failed all of the statistical tests we have
conducted and is therefore not suitable for stochastic simulations.
BBS also has a performance flaw since in practical use must be sufficiently
large (like tens or even hundreds of digits) to provide resistance from being
factorized in a short time.

** Next:** Statistical Tests
** Up:** Random Number Generators
** Previous:** TT800 and Mersenne Twister
2001-05-30