Liczba pseudolosowa to specjalna liczba generowana przez specjalny generator. Deterministyczny generator losowych bitów (PRNG), znany również jako deterministyczny generator losowych bitów (DRBG), to algorytm generowania sekwencji liczb, których właściwości są zbliżone do charakterystyk sekwencji liczb losowych. Wygenerowana sekwencja PRNG nie jest naprawdę losowa, ponieważ jest całkowicie określona przez wartość początkową zwaną ziarnem PRNG, która może zawierać wartości prawdziwie losowe. Chociaż sekwencje bliższe losowości można generować za pomocą sprzętowych generatorów liczb losowych, generatory liczb pseudolosowych są w praktyce ważne ze względu na szybkość generowania liczb i ich odtwarzalność.
Aplikacja
PRNG mają kluczowe znaczenie dla aplikacji takich jak symulacje (np. Monte Carlo), gry elektroniczne (np. do generowania proceduralnego) i kryptografia. Aplikacje kryptograficzne wymagają, aby dane wyjściowedane nie były przewidywalne na podstawie wcześniejszych informacji. Wymagane są bardziej złożone algorytmy, które nie dziedziczą liniowości prostych PRNG.
Regulamin
Dobre właściwości statystyczne są głównym warunkiem uzyskania PRNG. Ogólnie rzecz biorąc, potrzebna jest dokładna analiza matematyczna, aby upewnić się, że RNG generuje liczby, które są wystarczająco zbliżone do losowych, aby były odpowiednie do zamierzonego zastosowania.
John von Neumann ostrzegał przed błędną interpretacją PRNG jako prawdziwie losowego generatora i żartował, że „Każdy, kto rozważa metody arytmetyczne generowania liczb losowych, z pewnością jest w stanie grzechu”.
Użyj
PRNG można uruchomić z dowolnego stanu początkowego. Po zainicjowaniu w tym stanie zawsze wygeneruje tę samą sekwencję. Okres PRNG jest zdefiniowany następująco: maksimum we wszystkich stanach początkowych długości prefiksu niepowtarzającej się sekwencji. Okres jest ograniczony liczbą stanów, zwykle mierzonych w bitach. Ponieważ długość okresu potencjalnie podwaja się z każdym dodanym bitem „stanu”, łatwo jest tworzyć PRNG z okresami wystarczająco dużymi dla wielu praktycznych zastosowań.
Jeżeli stan wewnętrzny PRNG zawiera n bitów, jego okres nie może przekraczać 2n wyników, jest znacznie krótszy. W przypadku niektórych PRNG czas trwania można obliczyć bez pomijania całego okresu. Rejestry przesuwne z liniowym sprzężeniem zwrotnym (LFSR) są zazwyczajsą wybierane tak, aby miały okresy równe 2n − 1.
Liniowe generatory kongruencji mają okresy, które można obliczyć za pomocą faktoringu. Chociaż PPP powtórzy swoje wyniki po osiągnięciu końca okresu, powtórzenie wyniku nie oznacza, że został osiągnięty koniec okresu, ponieważ jego stan wewnętrzny może być większy niż wyjście; jest to szczególnie widoczne w przypadku PRNG z wyjściem jednobitowym.
Możliwe błędy
Błędy wykryte przez wadliwe PRNG wahają się od subtelnych (i nieznanych) do oczywistych. Przykładem jest algorytm liczb losowych RANDU, który jest używany na komputerach mainframe od dziesięcioleci. Była to poważna wada, ale jej nieadekwatność przez długi czas pozostawała niezauważona.
W wielu dziedzinach badania naukowe, w których zastosowano losowy dobór, symulacje Monte Carlo lub inne metody oparte na RNG, są znacznie mniej wiarygodne, niż mogłoby to wynikać ze słabej jakości GNPG. Nawet dzisiaj czasami wymagana jest ostrożność, o czym świadczy ostrzeżenie w Międzynarodowej Encyklopedii Nauk Statystycznych (2010).
Udane studium przypadku
Rozważmy powszechnie używany język programowania Java. Od 2017 r. Java nadal opiera się na Linear Congruential Generator (LCG) w zakresie PRNG.
Historia
Pierwszy PRNG, który pozwala uniknąć poważnych problemów i nadal działa dość szybko,był Mersenne Twister (omówiony poniżej), który został opublikowany w 1998 roku. Od tego czasu opracowano inne wysokiej jakości PRNG.
Ale historia liczb pseudolosowych na tym się nie kończy. W drugiej połowie XX wieku standardową klasą algorytmów stosowanych w PRNG były liniowe generatory kongruencyjne. Wiadomo, że jakość LCG jest niewystarczająca, ale lepsze metody nie były dostępne. Press et al (2007) opisali wynik w następujący sposób: „Jeśli wszystkie prace naukowe, których wyniki są wątpliwe z powodu [LCGs i pokrewnych], zniknęłyby z półek bibliotecznych, na każdej półce byłaby luka wielkości twojej pięści.”
Głównym osiągnięciem w tworzeniu generatorów pseudolosowych było wprowadzenie metod opartych na liniowych rekurencyjnych w polu dwuelementowym; takie oscylatory są sprzężone z rejestrami przesuwnymi z liniowym sprzężeniem zwrotnym. Były one podstawą do wynalezienia czujników liczb pseudolosowych.
W szczególności wynalazek firmy Mersen Twister z 1997 roku pozwolił uniknąć wielu problemów z wcześniejszymi generatorami. Mersenne Twister ma okres 219937-1 iteracji (≈4,3 × 106001). Udowodniono, że jest równomiernie rozłożony w (do) 623 wymiarach (dla wartości 32-bitowych) i w momencie jego wprowadzenia był szybszy niż inne statystycznie brzmiące generatory, które wytwarzają ciągi liczb pseudolosowych.
W 2003 roku George Marsaglia wprowadził rodzinę generatorów xorshift, również opartych na powtarzaniu liniowym. Te generatory są niezwyklesą szybkie i – w połączeniu z nieliniowym działaniem – przechodzą rygorystyczne testy statystyczne.
W 2006 roku opracowano rodzinę generatorów WELL. Generatory WELL w pewnym sensie poprawiają jakość Twistera Mersenne, który ma zbyt dużą przestrzeń stanów i bardzo powolne odzyskiwanie z nich, generując liczby pseudolosowe z dużą ilością zer.
Kryptografia
PRNG odpowiedni dla aplikacji kryptograficznych nazywa się kryptograficznie bezpiecznym PRNG (CSPRNG). Wymogiem CSPRNG jest to, że atakujący, który nie zna materiału siewnego, ma tylko marginalną przewagę w odróżnianiu sekwencji wyjściowej generatora od sekwencji losowej. Innymi słowy, podczas gdy PRNG jest wymagane tylko do przejścia niektórych testów statystycznych, CSPRNG musi przejść wszystkie testy statystyczne, które są ograniczone do czasu wielomianu w wielkości nasion.
Chociaż dowód tej właściwości wykracza poza obecny poziom teorii złożoności obliczeniowej, mocne dowody można dostarczyć, redukując CSPRNG do problemu uważanego za trudny, takiego jak faktoryzacja liczb całkowitych. Ogólnie rzecz biorąc, zanim algorytm może zostać certyfikowany jako CSPRNG, może być wymagany wieloletni przegląd.
Wykazano, że prawdopodobnie NSA umieściła asymetryczne tylne drzwi do generatora liczb pseudolosowych Dual_EC_DRBG z certyfikatem NIST.
Algorytmy pseudolosowenumery
Większość algorytmów PRNG tworzy sekwencje, które są równomiernie rozłożone w dowolnym z kilku testów. To jest pytanie otwarte. Jest to jeden z głównych elementów teorii i praktyki kryptografii: czy istnieje sposób na odróżnienie wyniku wysokiej jakości PRNG od naprawdę losowej sekwencji? W tym ustawieniu przelicznik wie, że albo został użyty znany algorytm PRNG (ale nie stan, w którym został zainicjowany), albo został użyty algorytm naprawdę losowy. Musi je rozróżniać.
Bezpieczeństwo większości algorytmów i protokołów kryptograficznych wykorzystujących PRNG opiera się na założeniu, że nie można odróżnić użycia odpowiedniego PRNG od użycia rzeczywiście losowej sekwencji. Najprostszymi przykładami tej zależności są szyfry strumieniowe, które najczęściej działają poprzez pominięcie lub wysłanie wiadomości w postaci zwykłego tekstu z wyjściem PRNG, tworząc zaszyfrowany tekst. Zaprojektowanie PRNG adekwatnych kryptograficznie jest niezwykle trudne, ponieważ muszą spełniać dodatkowe kryteria. Rozmiar tego okresu jest ważnym czynnikiem przydatności kryptograficznej PRNG, ale nie jedynym.
Wczesny PRNG komputerowy zaproponowany przez Johna von Neumanna w 1946 roku jest znany jako metoda średnich kwadratów. Algorytm jest następujący: weź dowolną liczbę, podnieś ją do kwadratu, usuń środkowe cyfry otrzymanej liczby jako „liczbę losową”, a następnie użyj tej liczby jako liczby początkowej do następnej iteracji. Na przykład kwadratura liczby 1111 daje1234321, który można zapisać jako 01234321, liczba 8-cyfrowa to kwadrat liczby 4-cyfrowej. Daje to 2343 jako liczbę „losową”. Wynik powtórzenia tej procedury to 4896 i tak dalej. Von Neumann użył 10-cyfrowych liczb, ale proces był taki sam.
Wady „środkowego kwadratu”
Problem z metodą średniej kwadratu polega na tym, że wszystkie sekwencje w końcu się powtarzają, niektóre bardzo szybko, na przykład: 0000. Von Neumann wiedział o tym, ale znalazł podejście wystarczające do jego celów i martwił się, że matematyczne „poprawki” po prostu ukryłyby błędy zamiast je usuwać.
Von Neumann stwierdził, że sprzętowe generatory liczb losowych i pseudolosowych są nieodpowiednie: jeśli nie rejestrują wygenerowanych danych wyjściowych, nie można ich później sprawdzić pod kątem błędów. Gdyby zapisali swoje wyniki, wyczerpaliby ograniczoną dostępną pamięć komputera, a tym samym zdolność komputera do odczytywania i zapisywania liczb. Gdyby liczby były zapisywane na kartach, ich pisanie i czytanie zajęłoby znacznie więcej czasu. Na komputerze ENIAC zastosował metodę „średniego kwadratu” i przeprowadził proces uzyskiwania liczb pseudolosowych kilkaset razy szybciej niż odczytywanie liczb z kart dziurkowanych.
Średni kwadrat został od tego czasu zastąpiony przez bardziej złożone generatory.
Innowacyjna metoda
Niedawną innowacją jest połączenie średniej kwadratowej z sekwencją Weila. Ta metoda zapewnia wysoką jakość produktów w ciągudługi okres. Pomaga uzyskać najlepsze formuły liczb pseudolosowych.
