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}}.$

Referências

• Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986.
• Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", Advances in Cryptology: Proceedings of Crypto '82. Available as PDF.
• Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. Available as PDF and Gzipped Postscript.

Ligações externas

• GMPBBS - uma implementação em GMP do Blum Blum Shub.
• Algoritmo Blum Blum Shub em Java
• Provas de aleatoriedade