Blum Blum Shub

Blum Blum Shub (BBS) é um gerador de números pseudoaleatórios proposto por Lenore Blum, Manuel Blum e Michael Shub em 1986.

O algoritmo BBS é:

x_n+1 = (x_n)² mod M

onde M=pq é o produto de dois números primos muito grandes p e q. Em cada passo do algoritmo, obtém-se um resultado para x_n; o resultado é geralmente o bit de paridade de x_n ou um ou mais dos bits menos significativos de x_n.

Os dois números primos, p e q, devem ser ambos congruentes a 3 (mod 4) (isto assegura que cada resíduo quadrático tenha uma raiz quadrada que também é um resíduo quadrático) e mdc (φ(p-1), φ(q-1)) deve ser pequena (isto faz que o comprimento do ciclo seja extenso).

Uma característica interessante do gerador BBS é a possibilidade de calcular todo o valor x_i de forma directa:

${\displaystyle x_{i}=\left(x_{0}^{2^{i}{\bmod {(}}p-1)(q-1)}\right){\bmod {M}}.}$