Blum Blum Shub

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

$x_{n+1}=(x_{n})^{2}{\bmod {M}},$

gdzie $x_{n}$ to kolejne stany, a $M$ to iloczyn dwóch dużych liczb pierwszych $p$ i $q$ dających w dzieleniu przez 4 resztę 3 (dzięki czemu każda reszta kwadratowa modulo $p$ ma jeden pierwiastek kwadratowy, który także jest resztą kwadratową), i mających możliwie mały $\operatorname {NWD} (\phi (p-1),\phi (q-1)),$ a $\phi$ 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. 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, M. Shub, A Simple Unpredictable Pseudo-Random Number Generator, „SIAM Journal on Computing”, vol. 15, s. 364–383, May 1986.

Zobacz też

• szyfr strumieniowy

Linki zewnętrzne

• GMPBBS.