Blum Blum Shub

Ten artykuł od 2012-09 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

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

gdzie ${\displaystyle x_{n}}$ to kolejne stany, a ${\displaystyle M}$ to iloczyn dwóch dużych liczb pierwszych ${\displaystyle p}$ i ${\displaystyle q}$ dających w dzieleniu przez 4 resztę 3 (dzięki czemu każda reszta kwadratowa modulo ${\displaystyle p}$ ma jeden pierwiastek kwadratowy, który także jest resztą kwadratową), i mających możliwie mały ${\displaystyle \operatorname {NWD} (\phi (p-1),\phi (q-1)),}$ a ${\displaystyle \phi }$ jest funkcją Eulera (co zapewnia długi cykl). Wynikiem generatora jest kilka ostatnich bitów ${\displaystyle 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 ${\displaystyle 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.

• szyfr strumieniowy

• GMPBBS.