Blum Blum Shub

Blum Blum Shub (BBS) est un algorithme capable de générer des nombres pseudo-aléatoires. Il fut proposé en 1986 par Lenore Blum, Manuel Blum et Michael Shub, d'où son nom.

On calcule la sortie de BBS en itérant la suite :

Avec $M=pq$, le produit de deux grands nombres premiers $p$ et $q$, et la sortie de l'algorithme est le bit le moins significatif (least signifiant bit ou LSB) de $x_n$. Alternativement, la sortie peut être plusieurs des derniers bits de $x_n$

Les deux nombres premiers, $p$ et $q$, devraient tous deux être congruents à 3 modulo 4 (cela garantit que chaque résidu quadratique possède une racine carrée qui possède également un résidu quadratique) et $\mathrm{pgcd}(\varphi (p-1),\varphi (q-1))$ doit être petit (ce qui fait que le cycle est long).

Le générateur n'est pas approprié aux simulations, mais plutôt à la cryptographie, car il est assez lent.

Cependant, il possède une sécurité inhabituelle, puisqu'il à été démontré qu'il était cryptographiquement sûr sous l'hypothèse qu'il soit difficile de factoriser un produit de grand nombres premiers, et que au plus $log(log(M))$ bits de poids faible de chaque $x_n$ soient sortis à chaque itération. Dans ce cas, il n'est pas possible de différencier la suite produite d'une suite réellement aléatoire.