Generatory liczb pseudolosowych

Obserwując świat fizyczny, wszędzie dostrzegamy fluktuacje losowe. Możemy generować prawdziwie losowe liczby, mierząc losowe fluktuacje nazywane szumem. A gdy mierzymy ten szum, co nazywa się próbkowaniem, możemy uzyskać liczby. Np. mierząc elektryczne parametry szumu telewizora w czasie, wygenerujemy prawdziwie losowy ciąg. Możemy wizualizować ten losowy ciąg, rysując ścieżkę, zmieniającą kierunek zależnie od każdej liczby. Nazywamy to błądzeniem losowym. Zauważcie brak wzoru w każdej skali. W każdym punkcie ciągu następny ruch jest nieprzewidywalny. Mówi się, że procesy losowe są niedeterministyczne, bo nie można zdeterminować ich zawczasu. Natomiast maszyny są deterministyczne. Ich działanie jest przewidywalne i powtarzalne. W 1946 r. John von Neumann prowadził obliczenia dla wojska; angażował się zwłaszcza w prace nad bombą wodorową. Za pomocą komputera ENIAC zamierzał powtarzalnie obliczać procesy związane z rozszczepieniem atomu. To jednak wymagało szybkiego dostępu do losowo generowanych liczb, które w razie potrzeby można powtórzyć. ENIAC miał bardzo ograniczoną pamięć wewnętrzną; przechowywanie długich ciągów losowych nie było możliwe. Neumann opracował więc algorytm, by mechanicznie symulować zagłuszający aspekt losowości: po pierwsze, wybieramy prawdziwie losową liczbę, zwaną ziarnem. Może to być wynik pomiaru szumu albo bieżący czas w milisekundach… To ziarno staje się przedmiotem prostego obliczenia. Pomnóżcie ziarno przez siebie i wyciągnijcie środkową część wyniku. Będzie to następne ziarno. Powtarzajcie proces, póki zachodzi potrzeba. To tzw. metoda środka kwadratu, pierwszy z długiego szeregu generatorów liczb pseudolosowych. Losowość ciągu zależy tylko od losowości pierwszego ziarna. To samo ziarno, ten sam ciąg. Jakie są więc różnice pomiędzy ciągami generowanymi losowo, a tymi generowanymi pseudolosowo? Wyraźmy każdy ciąg w postaci błądzenia losowego. Wydają się podobne, póki nie przyspieszymy. Sekwencja pseudolosowa w końcu musi się powtórzyć. To następuje, gdy algorytm sięga po ziarno, którego już używał, i cykl się powtarza. Długość fragmentu ciągu pseudolosowego, zanim się powtórzy, nazywamy okresem. Okres jest ograniczony przez długość pierwotnego ziarna. Np. jeśli używamy ziarna dwucyfrowego, to algorytm może wytworzyć co najwyżej 100 liczb, zanim ponownie wykorzysta ziarno i powtórzy cykl. Trzycyfrowe ziarno nie pozwoli na więcej niż 1000 liczb, zanim się powtórzy, a ziarno czterocyfrowe nie da ich więcej niż 10 tysięcy. Jednak przy dostatecznie dużym ziarnie ciąg może mieć nawet biliony cyfr, zanim się powtórzy. Najważniejsza różnica polega na tym: kiedy generujecie liczby pseudolosowo, wiele ciągów nie może się pojawić. Np. jeśli Alicja wygeneruje prawdziwie losowy ciąg dwudziestu podstawień i będzie on ekwiwalentem wyboru ze stosu wszystkich możliwych ciągów. Ten stos zawiera 26 do potęgi 20 kartek, co jest liczbą astronomiczną. Gdybyśmy stanęli u podnóża i poświecili latarką w górę, osoba na szczycie nie zobaczyłaby światła przez jakieś 200 milionów lat. Porównajcie to z Alicją generującą 20-literowy pseudolosowy ciąg przy użyciu czterocyfrowego losowego ziarna. To jest ekwiwalent wyboru z 10 tysięcy możliwych ziaren, co oznacza, że może ona wygenerować tylko 10 tysięcy różnych ciągów, a to znikoma część wszystkich możliwych ciągów. Kiedy przejdziemy od podstawień losowych do pseudolosowych, zmniejszymy przestrzeń kluczy do maleńkiego rozmiaru ziarna. Żeby ciąg pseudolosowy był nieodróżnialny od ciągu wygenerowanego losowo, dla komputera musi być niepraktyczne wypróbowywanie wszystkich ziaren i sprawdzanie, co pasuje. To prowadzi do ważnego w informatyce rozróżnienia między tym, co możliwe, a tym, co jest możliwe w rozsądnym czasie. Tę samą logikę stosujemy, kupując blokadę roweru. Wiemy, że każdy może wypróbować wszystkie możliwe kombinacje, aż znajdzie i blokada się otworzy. Ale trwałoby to kilka dni. Zakładamy, że przez 8 godzin jest bezpiecznie. Przy generatorach liczb pseudolosowych bezpieczeństwo rośnie wraz z długością ziarna. Gdyby najpotężniejszy komputer potrzebował setek lat na przeszukanie wszystkich ziaren, to możemy założyć, że szyfr jest bezpieczny „praktycznie”, choć nie „doskonale”. Gdy komputery działają szybciej, musi się zwiększać ziarno. Pseudolosowość uwalnia Alicję i Boba od konieczności dzielenia się zawczasu całym losowym ciągiem podstawiania. Oboje znają stosunkowo krótkie ziarno, i poszerzają je do takiego samego, wyglądającego na losowy, ciągu. A co, jeśli nie mogą się spotkać, by przekazać sobie to ziarno?