Blum Blum Shub

Szablon:Dopracować Blum Blum Shub – generator liczb pseudolosowych (PRNG) postaci:

$x_{n+1}=(x_n{)}^{2}modM,$

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 $\mathrm{NWD}(\varphi (p-1),\varphi (q-1)),$ a $\varphi$ 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

• Szablon:Cytuj stronę