Dlaczego nie można stworzyć prawdziwie losowych liczb?

Próbowałem rozwiązać problem hobby, który wymagał wygenerowania miliona losowych liczb. Ale szybko zdałem sobie sprawę, że trudno jest uczynić je wyjątkowymi. Wziąłem instrukcję projektowania algorytmów, aby przeczytać o generowaniu liczb losowych.

Ma następujący akapit, którego w pełni nie rozumiem.

Niestety generowanie liczb losowych wygląda o wiele łatwiej niż jest w rzeczywistości. Rzeczywiście, generowanie liczb losowych na dowolnym urządzeniu deterministycznym jest zasadniczo niemożliwe. Von Neumann [Neu63] powiedział to najlepiej: „Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu.” Najlepsze, na co możemy liczyć, to liczby pseudolosowe, strumień liczb, które wyglądają jak jeśli zostały wygenerowane losowo.

Dlaczego niemożliwe jest uzyskanie prawdziwie losowych liczb w jakimkolwiek deterministycznym urządzeniu? Co oznacza to zdanie?

Należy szukać kryptograficznie bezpiecznego generatora liczb pseudolosowych . Większość PRNG to liniowe generatory zgodności (więc next numberjest to funkcja liniowa previous number), więc jeśli narysujesz wykres next numbervs previous numberotrzymasz wykres równoległych linii. CSPRNG tego nie zrobi. Kompromis polega na tym, że są one powolne.

Generatory liczb losowych dzielę na 3 kategorie :

1. Wystarczająco dobry do odrabiania lekcji.
2. Wystarczająco dobry, aby postawić na swoją firmę.
3. Wystarczająco dobry, aby postawić swój kraj.

Dlaczego niemożliwe jest uzyskanie prawdziwie losowych liczb w jakimkolwiek deterministycznym urządzeniu?

Deterministyczne urządzenie zawsze będzie wytwarzało tę samą moc wyjściową, jeśli otrzyma takie same warunki początkowe i dane wejściowe - tak właśnie powinno być deterministic. „Prawdziwie losowa liczba” jest bardziej filozoficznym punktem widzenia, ponieważ to, co oznacza być, randomstanowi sedno filozoficznego patrzenia na pępek (ludzie nie są nawet pewni, czy rozpad atomowy jest losowy lub przebiega według jakiegoś wzoru, którego po prostu nie możemy zrozumieć jeszcze). Kryptograficznie bezpieczny generator liczb losowych pobierze jakieś zewnętrzne źródło entropii, aby urządzenie nie było deterministyczne.

Prawdziwa przypadkowość implikuje niedeterminizm. Jeśli jest deterministyczny, można go dokładnie przewidzieć (to właśnie oznacza determinizm); jeśli można to przewidzieć, nie jest losowy.

Najlepszą rzeczą, jaką można uzyskać od deterministycznego generatora liczb pseudolosowych, jest strumień liczb, który ma bardzo długi cykl (niepowtarzanie się jest niemożliwe, chyba że urządzenie RNG ma nieograniczoną pamięć), które przez cały cykl daje liczby strumieni spełniające wszystkie pozostałe właściwości losowej sekwencji (najbardziej interesujący jest jednolity rozkład wartości).

Aby rozwiązać ten problem, wiele współczesnych uniksów i systemów uniksowych ma RNG jądra, które wykorzystują fizyczne źródła hałasu do generowania prawdziwej losowości.

Innym powszechnym podejściem jest przyjmowanie bieżącego czasu jako zalążka deterministycznego RNG ( srand(time(NULL));w C); kryptograficznie rzecz biorąc, jest to bezwartościowe, ponieważ obecny czas nie jest tajemnicą, ale w przypadku takich rzeczy, jak symulacje fizyczne lub gry wideo, jest wystarczająco dobry.

Drugi rozdział książki Discrete-Event Simulation: A First Course autorstwa Lawrence'a Leemisa stanowi fantastyczne wprowadzenie do generatorów liczb losowych (a ściślej - generatorów liczb losowych psuedo).

Fragment jego książki wyjaśnia to dobrze moim zdaniem:

W przeszłości do zastosowań obliczeniowych zalecano trzy typy generatorów liczb losowych: (a) generatory przeglądające tablice w stylu lat 50. XX wieku, jak na przykład tablica korporacyjna RAND z milionem losowych cyfr; (b) generatory sprzętowe, takie jak na przykład termiczne urządzenia „białego szumu”; oraz (c) generatory algorytmiczne (programowe). Z tych trzech typów tylko generatory algorytmiczne uzyskały szeroką akceptację. Powodem tego jest to, że tylko generatory algorytmiczne mają potencjał do spełnienia wszystkich następujących ogólnie ogólnie przyjętych kryteriów generowania liczb losowych. Generator powinien być:

• random - zdolny do wytworzenia wyniku, który przejdzie wszystkie rozsądne statystyczne testy losowości;
• sterowalny - w razie potrzeby zdolny do odtworzenia swoich wyników;
• przenośny - zdolny do wytworzenia tej samej mocy wyjściowej w wielu różnych systemach komputerowych;
• wydajny - szybki, przy minimalnych wymaganiach dotyczących zasobów komputerowych;
• udokumentowane - teoretycznie przeanalizowane i szeroko przetestowane.

Tak więc chociaż możliwe byłoby użycie generatora szumów białych w celu uzyskania „lepszych” liczb losowych, nie zyskały one akceptacji, ponieważ nie spełniają większości powyższych kryteriów.

Radziłbym, abyś dostał kopię tej książki (lub czegoś podobnego). Zrozumienie, w jaki sposób praca PRNG z pewnością pomoże ci w twoich wysiłkach.

Ponieważ musisz napisać kod, aby wygenerować losowe liczby, a kod NIE jest losowy. (To deterministyczne)

Więc zaczynasz od „Wartości początkowych”, które są wybierane jako „Losowo” (zwykle aktualny znacznik czasu), a następnie używasz go w algorytmie, aby zacząć generować liczby. Ale cały zestaw oparty jest na oryginalnej wartości Seed!

Więc jeśli ponownie uruchomisz kod z dokładnie tymi samymi wartościami nasion, otrzymasz DOKŁADNY ten sam ZESTAW liczb! Jak każda rozsądna osoba może nazwać to przypadkiem? Ale to na pewno nie LOOK losowy.

Jeśli chodzi o uczynienie ich wyjątkowymi, po wygenerowaniu numeru po prostu sprawdź, czy już go masz, jeśli tak, wyrzuć go i wygeneruj nowy.

Ponieważ generujesz liczby losowe, należy oczekiwać, że wygenerowane wartości będą niejednoznaczne. Jest to właściwość losowości - nie można powiedzieć, że sekwencja liczb prawdziwie losowych (lub nawet pseudolosowych) jest unikalna, ponieważ wymaganie to pozwoliłoby przewidzieć końcową wartość w zakresie, a także zmienić prawdopodobieństwo wszystkie niezaznaczone liczby za każdym razem, gdy wybierany jest nowy.

Mam bardzo prostą definicję Pseudo Random :

Zbyt wiele nieznanych zmiennych do przewidzenia.

Mam również prostą definicję True Random :

Nieskończone nieznane zmienne.

Problem z komputerem polega na tym, że zawsze zna WSZYSTKIE zmienne. Liczba losowa jest po prostu funkcją matematyczną o pewnej wartości początkowej .
Najlepsze, co możemy zrobić, to podać komputerowi pseudolosową wartość początkową, która zwykle opiera się na zmiennej, której nie jesteśmy w stanie przewidzieć (takiej jak dokładny czas).

Mimo że komputer absolutnie nie jest w stanie utworzyć liczby losowej, dobrze jest wprowadzić zbyt wiele zmiennych, aby można było przewidzieć!

Generowanie prawdziwie losowych liczb w oprogramowaniu nie jest w rzeczywistości możliwe, jak zauważyli inni, jednak możliwe jest zbudowanie przez sprzęt urządzenia, które może generować prawdziwie losowe liczby *. Istnieje wiele takich przykładów w Internecie i istnieje wiele różnych metod, od odczytu czasu pomiędzy tyknięciami na liczniku Geigera do próbkowania białego szumu (głównie promieniowania tła z wszechświata) nieregulowanego odbiornika. Sam zbudowałem kilka przy użyciu kilku dostępnych metod.

* Każdy dobry maniak fizyki zwróci uwagę, że biorąc pod uwagę sposób działania wszechświata, żaden z nich nie jest naprawdę technicznie losowy, ale nie ma rozsądnego sposobu przewidzenia wyników, więc ze względu na tę dyskusję są wystarczające.

Nie ma możliwości wyprodukowania losowej liczby bez specjalnego sprzętu. W pierwszym roku studiów, z kilkoma kolegami z klasy, zaproponowaliśmy generator liczb losowych, który ma w zasadzie odbiornik AM i dostroił się do 4 różnych kanałów, dostał dane wejściowe do konwertera A na D i dodał je wszystkie (modulo do maksymalnej liczby). Ponieważ kombinacja wejścia analogowego z dowolnej dowolnej liczby stacji jest losowa i moglibyśmy wygenerować dużą liczbę liczb losowych z konwertera A2D, zaproponowaliśmy, że może to być dobry generator. Oczywiście nawet to nie jest przypadkowe w sensie filozoficznym, choć dla większości praktycznych celów może to zadziałać.

Determinizm jest zasadniczo funkcją. Pamiętaj z Algebry, że funkcja jest zgodnością między domeną i zakresem, że każdy członek domeny odpowiada dokładnie jednemu członkowi zakresu.

Więc jeśli f (x) = z, f (x)! = Y, chyba że y jest z. To jest funkcja. Wyobraź sobie JavaScript:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

Bez względu na to, ile razy wywołasz Add(2,3), zawsze zwróci 5. Innymi słowy, Add () jest funkcją deterministyczną.

Czynniki zewnętrzne mogą powodować, że Add zachowuje się w sposób niedeterministyczny. Na przykład, jeśli wprowadzisz wielowątkowość do równania. Wkład człowieka powoduje również niedeterminizm.

Teraz rzeczy stają się interesujące.

„Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu”.

Uwaga Von Neumann stwierdza: „arytmetyczne metody wytwarzania [...]”. Nie chodzi tu o wkład człowieka, współbieżność, przykładowe prędkości wiatru odczytane z precyzyjnego przyrządu lub inne nie algorytmiczne sposoby generowania losowego sygnału wejściowego do funkcji deterministycznej.

To po prostu stwierdza, że ​​funkcja lub system funkcji nie stanie się nagle niedeterministyczny. Innymi słowy, Add (2,3) nie zwróci w żaden sposób 6 ani niczego innego niż 5 przy tych samych danych wejściowych . To jest niemożliwe.

Cytujący autor idzie o krok dalej.

Najlepsze, na co możemy liczyć, to liczby pseudolosowe, strumień liczb, które wyglądają tak, jakby zostały wygenerowane losowo.

Kontekst został wcześniej zdefiniowany jako „na dowolnym deterministycznym urządzeniu”. Mógłbym zakończyć tę dyskusję tutaj. Ale co, jeśli zmienimy kontekst, wprowadzając nowy element do systemu? Element niedeterministyczny dodany jako dane wejściowe czyni system systemem niedeterministycznym. Jednak poprzez usunięcie elementu niedeterministycznego sprowadzamy się z powrotem do systemu deterministycznego. Jeśli potrafimy w jakiś sposób prześledzić lub w inny sposób odtworzyć dane wejściowe, możemy odtworzyć wynik. Cały ten akapit jest jednak ściśle związany z tym, co mówi autor. Zapamiętaj kontekst.

Można spierać się o znaczenie niedeterminizmu. Jeszcze raz tangetenial. Zapamiętaj kontekst.

Więc ma rację. Na żadnym deterministycznym urządzeniu układ deterministyczny nie może wygenerować prawdziwego losowego wyniku.