Blum Blum Shub

Blum Blum Shub to generator liczb pseudolosowych (PRNG) postaci:

$x_{n+1} = (x_n)^2 \,\operatorname{mod}\, M$

gdzie $x n$ to kolejne stany, zaś $M$ to iloczyn dwóch dużych liczb pierwszych dających w dzieleniu przez 4 resztę 3, i mających możliwie mały $\operatorname{NWD}(\phi(p-1),\phi(q-1))$ , a $φ$ jest funkcją Eulera (co zapewnia długi cykl). Wynikiem generatora jest kilka ostatnich bitów $x n$ .

Generator ten jest dość powolny, za to bardzo bezpieczny. Przy odpowiednich założeniach, odróżnienie jego wyników od szumu jest równie trudne jak faktoryzacja $M$ , tak więc jest stosowany głównie w kryptografii. Oczywiście może się zdarzyć, że znaleziony zostanie szybki algorytm faktoryzacji i Blum Blum Shub przestanie być bezpieczny.

Algorytm został po raz pierwszy opisany w pracy:

L. Blum, M. Blum, and M. Shub.

A Simple Unpredictable Pseudo-Random Number Generator.

SIAM Journal on Computing, vol. 15, p. 364-383, May 1986