Blum Blum Shub

---

Blum Blum Shub ( BBS ) es un generador de números pseudoaleatorios propuesto en 1986 por Lenore Blum , Manuel Blum y Michael Shub ^[1] que se deriva de la función unidireccional de Michael O. Rabin .

donde M = pq es el producto de dos primos grandes p y q . En cada paso del algoritmo, se deriva alguna salida de x _{n +1} ; la salida suele ser la paridad de bits de x _{n +1} o uno o más de los bits menos significativos de x _{n +1}.

La semilla x ₀ debe ser un número entero coprimo de M (es decir, p y q no son factores de x ₀ ) y no 1 o 0.

Los dos primos, p y q , deben ser congruentes con 3 (mod 4) (esto garantiza que cada residuo cuadrático tenga una raíz cuadrada que también es un residuo cuadrático), y deben ser primos seguros con mcd pequeño (( p- 3 ) /2 , ( q-3 ) /2 ) (esto hace que la duración del ciclo sea grande).

Una característica interesante del generador Blum Blum Shub es la posibilidad de calcular cualquier valor x _i directamente (a través del teorema de Euler ):

donde es la función de Carmichael . (Aquí tenemos ).${\ estilo de visualización \ lambda}$${\displaystyle \lambda (M)=\lambda (p\cdot q)=\operatorname {lcm} (p-1,q-1)}$

---