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:
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 modulo 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, 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.