Blum Blum Shub

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 é:

xn+1 = (xnmod 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 xn; o resultado é geralmente o bit de paridade de xn ou um ou mais dos bits menos significativos de xn.

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 xi de forma directa:

 x_i = \left( x_0^{2^i \bmod (p-1)(q-1)} \right) \bmod M.

Referências[editar | editar código-fonte]

  • 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[editar | editar código-fonte]