6.1.7 Blum-Blum-Shub Generator
The Blum-Blum-Shub pseudo random number generator is cryptologically
secure under the assumption that the quadratic residuosity problem is
intractable [8]. The algorithm consists of the following:
- Generate two large and distinct primes, p and q, each congruent to
3 mod 4.
Define m = pq.
- Select a seed s taking a value between 1 and m-1,
such that the greatest common divisor between s and m is
1.
- Let
x(0) = s * s mod m. For i = 1,2,... generate x(i) = x(i-1) * x(i-1) mod m,
z(i) = v least significant bits of x(i).
where v>=1
.
- The bit-sequence
z(1),z(2),z(3), ...
is then the output sequence used.