Blum Blum Shub

Blum Blum Shub (BBS) es un generador pseudoaleatorio de números propuesto por Lenore Blum, Manuel Blum y Michael Shub en 1986.

El algoritmo BBS es:

x_n+1 = (x_n)² mod M

donde M=pq es el producto de dos números primos muy grandes p y q. En cada paso del algoritmo, se obtiene un resultado para x_n; el resultado es por lo general o bien el bit de paridad de x_n ó uno o más de los bits menos significativos de x_n.

Los dos números primos, p y q, deben ser ambos congruentes a 3 (mod 4) (esto asegura que cada residuo cuadrático posee una raíz cuadrada que también es un residuo cuadrático) y mcd(φ(p-1), φ(q-1)) debe ser pequeña (esto hace que la longitud del ciclo sea extensa).

Una característica interesante del generador BBS es la posibilidad de calcular todo valor x_i en forma directa:

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