Blum Blum Shub

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Blum Blum Shubgenerator liczb pseudolosowych (PRNG) postaci:

gdzie to kolejne stany, a to iloczyn dwóch dużych liczb pierwszych i dających w dzieleniu przez 4 resztę 3 (dzięki czemu każda reszta kwadratowa ma jeden pierwiastek kwadratowy, który także jest resztą kwadratową), i mających możliwie mały , a jest funkcją Eulera (co zapewnia długi cykl). Wynikiem generatora jest kilka ostatnich bitów .

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 , tak więc jest stosowany głównie w kryptografii. 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

Zobacz też[edytuj]

Linki zewnętrzne[edytuj]