Blum Blum Shub
# 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:
    $x_{i}=\left(x_{0}^{2^{i}{\bmod {}p-1)(q-1)}\right){\bmod {M}}.$