Jakiś facet powiedział:

Każdy, kto próbuje generować losowe liczby za pomocą deterministycznych środków, oczywiście żyje w stanie grzechu.

To zawsze oznacza, że ​​nie można wygenerować prawdziwych liczb losowych za pomocą samego komputera. Powiedział też, że gdy komputery były równoważnej wielkości pojedynczego mikroprocesora Intel 8080 (~ 6000 zaworów). Komputery stały się bardziej złożone i uważam, że stwierdzenie von Von Neumanna może już nie być prawdziwe. Weź pod uwagę, że zaimplementowany algorytm programowy jest niemożliwy. Działają na fizycznym sprzęcie. Prawdziwe generatory liczb losowych i ich źródła entropii są również wykonane ze sprzętu.

Ten fragment Java umieszczony w pętli:

      file.writeByte((byte) (System.nanoTime() & 0xff));

mogę utworzyć plik danych, który przedstawiłem jako obraz:

Możesz zobaczyć strukturę, ale także z dużą przypadkowością. Interesujące jest to, że ten plik PNG ma rozmiar 232 KB, ale zawiera 250 000 pikseli w skali szarości. Poziom kompresji PNG był maksymalny. To tylko współczynnik kompresji 7%, tj. dość nieściśliwy. Co ciekawe, plik jest unikalny. Każda generacja tego pliku ma nieco inny wzorzec i ma podobną ~ 7% kompresowalność. Podkreślam to, ponieważ ma to kluczowe znaczenie dla mojej argumentacji. To entropia ~ 7 bitów / bajt. Zmniejszy to oczywiście użycie silniejszego algorytmu kompresji. Ale nie redukuj do niczego w pobliżu 0 bitów / bajt. Lepsze wrażenie można uzyskać, wykonując powyższe zdjęcie i zastępując jego mapę kolorów losową: -

Większość struktury (w górnej połowie) znika, ponieważ były to tylko sekwencje o podobnych, ale nieznacznie różnych wartościach. Czy to jest prawdziwe źródło entropii utworzone po prostu przez uruchomienie programu Java w systemie operacyjnym z wieloma opcjami? Nie jednolicie rozłożony generator liczb losowych, ale źródło entropii dla jednego? Źródło entropii zbudowane z oprogramowania działającego na fizycznym sprzęcie, który akurat jest komputerem.

Uzupełniający

Aby potwierdzić, że każdy obraz generuje świeżą entropię bez ustalonego wzoru wspólnego dla wszystkich, wygenerowano 10 kolejnych obrazów. Zostały one następnie połączone i skompresowane za pomocą najsilniejszego archiwizatora, jaki mogę skompilować (paq8px). Proces ten wyeliminuje wszystkie typowe dane, w tym autokorelację, pozostawiając jedynie zmiany / entropię.

Skonsolidowany plik jest skompresowany do ~ 66%, co prowadzi do szybkości entropii wynoszącej ~ 5,3 bitu / bajt lub 10,5 Mb / obraz. Zaskakująca ilość entropii$\smile$

Uzupełnienie 2

Pojawiły się negatywne komentarze, że moja entropia metodologii testów kompresji jest wadliwa, dając jedynie luźne oszacowanie górnej granicy. Uruchomiłem więc skonkatenowany plik przez oficjalny test oceny entropii kryptograficznej NIST, SP800-90B_EntropyAssessment . Jest to tak dobre, jak to możliwe do pomiaru entropii bez IID. To jest raport (przepraszam, że to pytanie jest długie, ale problem jest złożony): -

Running non-IID tests...

Entropic statistic estimates:
Most Common Value Estimate = 7.88411
Collision Test Estimate = 6.44961
Markov Test Estimate = 5.61735
Compression Test Estimate = 6.65691
t-Tuple Test Estimate = 7.40114
Longest Reapeated Substring Test Estimate = 8.00305

Predictor estimates:
Multi Most Common in Window (MultiMCW) Test: 100% complete
    Correct: 3816
    P_avg (global): 0.00397508
    P_run (local): 0.00216675
Multi Most Common in Window (Multi MCW) Test = 7.9748
Lag 

Test: 100% complete
    Correct: 3974
    P_avg (global): 0.00413607
    P_run (local): 0.00216675
Lag Prediction Test = 7.91752
MultiMMC Test: 100% complete
    Correct: 3913
    P_avg (global): 0.00407383
    P_run (local): 0.00216675
Multi Markov Model with Counting (MultiMMC) Prediction Test = 7.9394
LZ78Y Test: 99% complete
    Correct: 3866
    P_avg (global): 0.00402593
    P_run (local): 0.00216675
LZ78Y Prediction Test = 7.95646
Min Entropy: 5.61735

W rezultacie NIST uważa, że ​​wygenerowałem 5,6 bitów / bajt entropii. Mój szacunek kompresji DIY określa to na 5,3 bitów / bajt, nieco bardziej konserwatywny.

-> Dowody wydają się potwierdzać pogląd, że komputer z uruchomionym oprogramowaniem może generować prawdziwą entropię. I że von Neumann się mylił (ale może słusznie jak na swój czas).

Oferuję następujące referencje, które mogą potwierdzić moje roszczenie:

Czy istnieją jakieś stochastyczne modele niedeterminizmu w tempie wykonywania programu?

Analiza WCET probabilistycznych twardych systemów czasu rzeczywistego

Czy istnieje algorytm programowy, który może generować niedeterministyczny wzorzec chaosu? i znaczenie efektów chaotycznych.

Podobieństwa z kwantową zasadą niepewności entropijnej

Wpis na blogu Aleksey Shipilёv dotyczący chaotycznego zachowania nanoTime (). Jego fabuła rozproszenia nie różni się od mojej.

To, że nie widzisz wzoru, nie oznacza, że ​​nie istnieje. To, że algorytm kompresji nie może znaleźć wzorca, nie oznacza, że ​​nie ma wzorca. Algorytmy kompresji nie są srebrnymi kulami, które mogą w magiczny sposób zmierzyć prawdziwą entropię źródła; wszystko, co ci dają, to górna granica wielkości entropii. (Podobnie, test NIST daje ci tylko górną granicę.) Chaos nie jest przypadkowy.

Bardziej szczegółowa analiza i badanie wymaga pewności co do jakości losowości uzyskanej w ten sposób.

Tam są powody, by sądzić, że możemy prawdopodobnie uzyskać pewną ilość losowości wykorzystując zegar jitter i dryfowania pomiędzy dwoma zegarami sprzętowych , ale delikatne i trudne, więc trzeba być ostrożnym. Nie zalecałbym próby wdrożenia własnego. Zamiast tego sugeruję użycie wysokiej jakości źródła entropii (zwykle implementowanego w większości nowoczesnych systemów operacyjnych). Aby uzyskać więcej informacji, zobacz także Wikipedię , haveged i /crypto//q/48302/351 (co wydaje się, że już wiesz).

Na koniec komentarz do twojego otwieracza:

„Każdy, kto próbuje generować losowe liczby za pomocą deterministycznych środków, oczywiście żyje w stanie grzechu”.

To zawsze oznacza, że ​​nie można wygenerować prawdziwych liczb losowych za pomocą samego komputera.

Nie, zwykle nie tak to się bierze i nie tak to mówi. Mówi, że nie można wygenerować prawdziwych liczb losowych za pomocą metod deterministycznych . To, czy możesz to zrobić na komputerze, zależy od tego, czy komputer jest deterministyczny, czy nie. Jeśli komputer jest deterministyczny lub twój program używa tylko operacji deterministycznych, nie możesz. Jednak wiele komputerów zawiera niedeterministyczne elementy, a jeśli twój program ich używa, konieczna jest bardziej szczegółowa analiza, zanim zdecydujesz, czy można ich użyć do generowania liczb losowych. W twoim przypadku nanoTime()jest niedeterministyczny.

Jeśli używasz jakiegoś sprzętowego źródła entropii / losowości, nie „próbujesz generować losowości za pomocą deterministycznych środków” (moje podkreślenie). Jeśli nie używasz żadnego sprzętowego źródła entropii / losowości, mocniejszy komputer oznacza po prostu, że możesz popełnić więcej grzechów na sekundę.

Zawsze rozumiałem, że cytat oznacza, że ​​algorytm deterministyczny ma ustaloną ilość entropii i chociaż dane wyjściowe mogą wydawać się „losowe”, nie mogą zawierać więcej entropii niż dane wejściowe. Z tej perspektywy widzimy, że twój algorytm szmugluje się w entropii poprzez System.nanoTime()- większość definicji algorytmu „deterministycznego” uniemożliwia wywołanie tej funkcji.

Cytat - choć zwięzły - jest w gruncie rzeczy tautologią. Nie ma nic do obalenia i nie jest możliwa ewolucja sprzętu, która może sprawić, że przestanie być prawdziwa. Nie chodzi o sprzęt, chodzi o definicję algorytmu deterministycznego. Po prostu zauważa, że ​​determinizm i przypadkowość są niezgodne. Dla każdego algorytmu deterministycznego całe jego zachowanie jest przewidywane na podstawie warunków początkowych. Jeśli uważasz, że znalazłeś wyjątek, nie rozumiesz, co to znaczy być deterministycznym.

Prawdą jest, że proces działający na wspólnym komputerze ze złożoną serią pamięci podręcznych, który odbiera różne dane wejściowe z sieci i sprzętu, ma dostęp do znacznie większej entropii niż proces działający na prostym, izolowanym, dedykowanym sprzęcie. Ale jeśli ten proces uzyskuje dostęp do tej entropii, nie jest już deterministyczny, więc cytat nie ma zastosowania.

Każdy, kto próbuje generować losowe liczby za pomocą deterministycznych środków, oczywiście żyje w stanie grzechu.

Kiedy interpretujesz „życie w stanie grzechu” jako „robienie bzdur”, jest to całkowicie słuszne.

To, co zrobiłeś, to użycie raczej powolnej metody System.nanoTime()do generowania raczej słabej losowości. Zmierzyłeś trochę

... szybkość entropii ~ 5,3 bitów / bajt ...

ale to tylko górna granica. Wszystko, co możesz dostać, to górna granica. Rzeczywista entropia może być o rząd wielkości mniejsza.

Zamiast tego spróbuj wypełnić tablicę za pomocą skrótu kryptograficznego, takiego jak MD5. Oblicz sekwencję jak md5(0), md5(1), ...(z każdej wartości pobranej jeden lub więcej bajtów, to nie ma znaczenia). W ogóle nie uzyskasz żadnej kompresji (tak, MD5 jest zepsuty, ale wciąż wystarczająco dobry, aby wytworzyć dane nieściśliwe).

Można powiedzieć, że w ogóle nie ma entropii, ale zmierzyłbyś 8 bitów / bajt.

Kiedy naprawdę potrzebujesz czegoś losowego, musisz nie tylko skorzystać ze źródła HW, ale także znać pewną dolną granicę tego, ile entropii faktycznie wytwarza. Chociaż najprawdopodobniej jest w tym pewna przypadkowość nanoTime(), nie jestem świadomy żadnej nietrywialnej dolnej granicy.

Kiedy potrzebujesz losowości w kryptografii, musisz naprawdę skorzystać z czegoś, co zapewnia twój system operacyjny, język lub dobra biblioteka. Tacy dostawcy zbierają entropię z wielu źródeł i / lub dedykowanego sprzętu i do takich oszacowań entropii włożono sporo pracy.

Pamiętaj, że zwykle nie potrzebujesz prawie żadnej entropii. Dobry (deterministyczny) PRNG zainicjowany kilkoma losowymi bajtami nadaje się do kryptografii, a zatem także do wszystkiego innego.

Myślałem, że zacznę rozumieć znaczenie słowa „losowy”. Większość odpowiedzi tutaj mówi o wyniku procesów losowych , w porównaniu do wyników procesów deterministycznych. To całkiem dobre znaczenie „losowy”, ale nie tylko.

Jednym z problemów związanych z wynikami procesów losowych jest to, że trudno je odróżnić od wyników procesów deterministycznych: nie zawierają one „zapisu” losowości ich źródła. Skrajnym przykładem tego jest słynny komiks XKCD, w którym generator liczb losowych zawsze powraca 4, a komentarz kodu twierdzi, że jest losowy, ponieważ pochodzi z rzutu kostką.

Alternatywne podejście do definiowania „losowości”, zwanej złożonością Kołmogorowa , opiera się na samych danych, niezależnie od tego, jak zostały wygenerowane. Złożoność Kołmogorowa niektórych danych (np. Ciąg liczb) jest długością najkrótszego programu komputerowego, który wyprowadza te dane: dane są „bardziej losowe”, jeśli mają wyższą złożoność Kołmogorowa.

Korzystanie z algorytmów kompresji, takich jak PNG, i porównywanie długości przed kompresją i po niej jest podobne do złożoności Kołmogorowa. Jednak złożoność Kołmogorowa pozwala na kodowanie danych jako program w dowolnym języku programowania Turinga, a nie w ograniczonym formacie, takim jak PNG; „dekompresowanie” takich kodowań (programów) odbywa się przez ich uruchomienie, co może zająć dowolną ilość czasu i pamięci (np. więcej niż jest dostępne w naszym małym wszechświecie).

Twierdzenie Rice'a mówi nam, że generalnie nie możemy rozróżnić programów, które zapętlają się na zawsze, i programów, które generują nasze dane. Dlatego bardzo trudno jest znaleźć złożoność niektórych danych Kołmogorowa: jeśli zanotujemy program, który generuje te dane, może istnieć program krótszy (tj. O mniejszej złożoności), ale nie zauważyliśmy go, ponieważ nie mogliśmy odróżnij go od nieskończonej pętli. Złożoności Kołmogorowa nie można zatem obliczyć, chociaż gdybyśmy znali liczby Busy-Beaver , moglibyśmy je obliczyć, wykorzystując je do ograniczenia czasu sprawdzania każdego programu.

W przypadku twoich przykładowych danych, aby znaleźć jego złożoność Kołmogorowa (tj. „Losowość wewnętrzną”), musielibyśmy znaleźć najkrótszy program deterministyczny, który wyprowadza tę samą sekwencję bajtów i przyjmowałby jego długość.

Teraz możemy odpowiedzieć na twoje pytanie z punktu widzenia złożoności Kołmogorowa i stwierdzimy, że cytat jest poprawny: nie możemy wygenerować liczb losowych (wysoka złożoność Kołmogorowa) za pomocą metod deterministycznych.

Dlaczego nie? Wyobraźmy sobie, że piszemy mały program komputerowy i używamy go do generowania sekwencji liczb losowych. Musi mieć zastosowanie jedna z następujących sytuacji:

• Generujemy ogromną ilość produkcji. Ponieważ jednak wiemy, że dane wyjściowe są generowane przez mały program, dane wyjściowe (z definicji) mają niską złożoność Kołmogorowa, a zatem nie są w tym sensie „losowe”.
• Generujemy tak mało liczb, że spisanie ich wszystkich zajęłoby mniej więcej tyle samo lub mniej niż zapisanie naszego krótkiego programu generującego. W tym przypadku liczby są stosunkowo nieściśliwe, co wskazuje, że są one dość losowe w sensie Kołmogorowa. Ponieważ jednak ilość danych wyjściowych jest porównywalna z tym, co wprowadziliśmy (kod źródłowy programu), można śmiało powiedzieć, że program nie „wygenerował” losowości, zrobiliśmy to, wybierając ten program. Wszakże w tym przypadku nasz program generujący równie dobrze mógłby być listą tych dokładnych liczb (np print([...]).).

W obu przypadkach nie „generujemy” więcej losowości, niż wprowadzamy („losowość” kodu źródłowego naszego programu generującego). Możemy spróbować obejść ten problem, używając programu o dłuższym czasie generowania, aby uniknąć generowania krótkiego generatora, ale są tylko dwa sposoby:

• Systematycznie „wypycha” kod w jakiś sposób. Jednak złożoność Kołmogorowa nie dba o konkretny program, którego użyliśmy do wygenerowania danych: dba tylko o to, który program generujący jest najmniejszy. Systematyczne wzdęcie nie dodaje złożoności Kołmogorowa, ponieważ takie wzorce w kodzie mogą być generowane przy użyciu bardzo małej ilości kodu. Na przykład, jeśli weźmiemy run(shortGenerator)i dodamy cały ładunek systematycznego wzdęcia, aby uzyskać run(bloatedGenerator), nadal istnieje krótki generator formularza run(addBloat(shortGenerator)).
• Dodawaj wzdęcia niesystematycznie , tzn. Bez żadnych wzorców, aby addBloatfunkcja musiała skończyć tak samo rozdęta jak sam kod. Jednak bycie tak pozbawionym wzorów jest dokładnie tym, co czyni coś losowym (wysoka złożoność Kołmogorowa). Stąd wzdęcia program generujący w ten sposób powoduje zwiększenie losowości (Złożoność Kołmogorowa) wyjścia, ale również zwiększa ilość losowości (Złożoność Kołmogorowa), że musimy zapewnić w postaci kodu źródłowego. Dlatego to my zapewniamy „losowość”, a nie program. W powyższym przykładzie zwykłego pisania print([...])dodanie niesystematycznego wzdęcia jest równoznaczne z zapisaniem większej liczby „losowych” liczb na tej zakodowanej liście.

Kompresja nie jest dokładnym testem losowości, ani też nie patrzy na obraz i nie mówi „to wygląda losowo”.

Losowość jest sprawdzana metodami empirycznymi . W rzeczywistości istnieją zestawy specjalnie zaprojektowanego oprogramowania / algorytmów do testowania losowości, na przykład TestU01 i testy Dieharda .

Co więcej, twój obraz jest w rzeczywistości ciągiem 1D liczby odwzorowanej na spację, a zatem nie jest dobrą reprezentacją pewnych wzorów, które mogą się pojawić.

Jeśli miałbyś badać obraz piksel po pikselu, najprawdopodobniej znalazłbyś wiele krótkich wzorów o rosnącej wartości przed nagłym spadkiem. Jeśli utworzysz wykres z wartością x będącą liczbą próbek, a wartością y będącą wartością uzyskaną z funkcji „losowej”, najprawdopodobniej odkryjesz, że twoje dane w rzeczywistości wyglądają jak fala piłokształtna:

Jest to wzorzec utworzony przez wartości, które rosną zgodnie z arytmetyką modułową (którą twoje obliczenia są przykładem: wzrostu czasu z prawie stałą szybkością i & 0xFFdziałania jako mod 256).

Mylisz pojęcie liczb losowych z „liczb, które wydają się losowe”.

Aby zrozumieć cytat von Neumanna, musimy zrozumieć, co to znaczy „generować liczby losowe”. Odpowiedź Warbo łączy w tym celu doskonały XKCD :

Kiedy mówimy o liczbach losowych, nie mówimy o samych wartościach. Oczywiście 4 nie jest bardziej losowe niż 3. Mówimy o zdolności osoby trzeciej do przewidywania tej wartości lepiej niż przypadkowa szansa. Liczba losowa to taka, której nie można przewidzieć. Czasami dodamy do tego warunki. Kryptograficznie bezpieczny generator liczb pseudolosowych (CSPRNG) generuje liczby, których nie można przewidzieć lepiej niż przypadkowa szansa, jeśli atakujący nie zna nasienia / klucza, ale jeśli mówimy o liczbach prawdziwie losowych (nie pseudolosowych), zwykle jest definiowany jako liczba, której nie można przewidzieć, nawet przy pełnej znajomości systemu, w tym wszelkich kluczy.

Twój przykład, jak wielu zauważyło, nie jest deterministyczny. Program nie określa, z jakiej wartości pochodzi System.nanoTime(). Zatem nie należy do tej samej klasy co używanie CSPRNG do generowania liczb pseudolosowych. Pierwszy może być niedeterministyczny, a drugi deterministyczny, jeśli wartość klucza jest deterministyczna. Pierwsza zawiera operacje, które nie są zdefiniowane jako mające wartości deterministyczne.

Zauważysz jednak, że powiedziałem, że może to być niedeterministyczne. Należy pamiętać, że System.nanoTime()nie ma to na celu dostarczenia wartości do tego celu. Może, ale nie musi być wystarczająco niedeterministyczny. Aplikacja może tak dostosować zegar systemowy, aby wywołania System.nanoTime()wszystkich występowały z wielokrotnością 256 nanosekund (lub blisko). Lub możesz pracować w Javascripcie, gdzie ostatnie exploity Spectre spowodowały, że główne przeglądarki celowo zmniejszyły rozdzielczość swoich timerów. W takich przypadkach Twoje „liczby losowe” mogą stać się wysoce przewidywalne w środowiskach, których nie planowałeś.

• Generowanie liczb losowych z deterministycznymi procesami ... grzech.
• Generowanie liczb losowych za pomocą dedykowanego sprzętu losowego ... a nie grzechu.
• Generowanie liczb losowych z niedeterministycznymi aspektami komputerów ... może grzech.

Wszystko zależy od tego, co zamierzasz. Jeśli szyfrujesz swoje listy miłosne do Sponge Bob, aby twoja siostra nie mogła ich odczytać, wymagania wobec twoich tak zwanych liczb losowych są dość niskie. System.nanoTime()użyty tak jak ty prawdopodobnie jest wystarczająco dobry. Jeśli chronisz tajemnice nuklearne przed zaawansowanym obcym państwem, które ich aktywnie poszukuje, możesz rozważyć użycie sprzętu zaprojektowanego tak, aby sprostał wyzwaniu.

Nie sądzę, że zrozumiałeś roszczenie. Chodzi o to, że jeśli istnieje deterministyczna procedura generowania „losowej” serii liczb (lub cokolwiek, naprawdę), to znalezienie wzoru jest jedynie zadaniem znalezienia tej procedury!

Dlatego zawsze istnieje deterministyczna metoda przewidywania następnej liczby całkowitej. Właśnie tego nie spodziewamy się, jeśli założymy przypadkowość!

Każda wystarczająco złożona deterministyczność jest nie do odróżnienia od stochastyczności.

- Ze strony użytkownika Wrzlprmft

Dlatego nawet jeśli coś wygląda losowo, dlaczego, u licha, mielibyśmy go modelować jako „losowy”, jeśli mamy deterministyczną procedurę jego wygenerowania?

Myślę, że to kluczowy problem. Pokazałeś tylko jakąś formę nierozróżnialności PRNG i „prawdziwej losowości”.

Jednak to, że te pojęcia są równe, nie następuje. W szczególności przypadkowość jest matematyczną, teoretyczną koncepcją. Pokazaliśmy już powyżej, że teoretycznie uznanie PRNG za „prawdziwą przypadkowość” prowadzi do sprzeczności. Dlatego nie mogą być równi.

Myślę, że inni już to zauważyli, ale to nie podkreśla, więc dodam jeszcze do dyskusji.

Jak już zauważyli inni, istnieje problem pomiaru entropii. Algorytmy kompresji mogą ci coś powiedzieć, ale są niezależne od źródła. Ponieważ wiesz więcej na temat tego, jak dane zostały wygenerowane, prawdopodobnie można by to zrobić znacznie lepiej algorytm do ich kompresji, a to oznacza, że ​​prawdziwa entropia jest znacznie niższa.

Co więcej, mylisz się co do znaczeń wyrażeń „na komputerze” i „deterministyczny”. Z pewnością możesz wykonać niedeterministyczny operację na komputerze.

Co więcej, właśnie to zrobiłeś , ale na pierwszy rzut oka nie jest to takie oczywiste.

Typowy deterministyczny algorytmem do generowania liczb losowych jest np. PRNG jak liniowy generator kongruencjalny. Są stanowe. Stan wewnętrzny oznacza mniej entropii, ponieważ następny stan jest określany przez poprzedni. Nie zagłębię się w to, prawdopodobnie dla ciebie to oczywiste. Ważne jest to, że w pełni deterministyczny algorytm zależy tylko od poprzedniego stanu, cokolwiek by to było.

Teraz spójrz na swój algorytm. Na czym się opiera? Ile masz stanów? Czy to jest deterministyczne?

  file.writeByte((byte) (System.nanoTime() & 0xff));

Zignorujmy file.writei wszelkie problemy związane z opróżnianiem buforów, czekając na I / O (próbowałeś przez chwilę dodać duży szum na kablach dysku twardego? Nie? Hej, możesz to zrobić. Hej, to nie jest deterministyczne! :)), i skupmy się na źródle, to jest ważniejsze.

Czas jest jakiś stan. Różni się, ale większość jest taka sama. Dlatego próbowałeś go obejść i wziął & 0xFF, aby usunąć większość stanu. Ale nie upuściłeś tego wszystkiego, jakiś stan z poprzedniego odczytu może przeciekać do następnego, więc na pewno nie jest to całkowicie niedeterministyczne *)

Ale nie jesteśmy tym zainteresowani. Aby „udowodnić”, że cytat jest błędny:

Każdy, kto próbuje generować losowe liczby za pomocą deterministycznych środków, oczywiście żyje w stanie grzechu.

Musisz to udowodnić deterministycznie.
Interesuje nas to: czy twoje algo jest z pewnością w pełni deterministyczne ?

.. i jest oczywiste, że tak nie jest.

  System.nanoTime() & 0xff

To pomiar czasu. Czas i pomiar . Część pomiaru może uczynić ją deterministyczną, jeśli wartość jest buforowana. Zakładam, że tak nie jest, w przeciwnym razie funkcja ta nie miałaby sensu. Następnie, jeśli jest on odczytywany w locie ze źródła, mamy wartość czasową. Ponieważ ( ponownie zakładam ) nie uruchomiłeś tego na dedykowanym sprzęcie jednozadaniowym, czasami możesz mieć do czynienia z przełączaniem kontekstu. Nawet jeśli masz dedykowany sprzęt do jednego zadania, pomiar czasu może nadal nie być deterministyczny, ze względu na zmiany temperatury / wilgotności w źródle czasu, czasy taktowania magistrali itp.

Całkowicie się zgadzam, że przesadzam. Dryfy nie będą tak duże, aby wywrzeć duży wpływ (choć tak naprawdę nanotimemogą być). Co ważniejsze, nanotimema być szybki. Nie czyta ze źródła czasu rzeczywistego. Opiera się na wewnętrznej instrukcji procesora / liczbie cykli. To jest rzeczywiście deterministyczne, jeśli nie zapewnisz przełączania kontekstu.

Chodzi mi o to, że uruchomienie naprawdę w 100% deterministycznego algorytmu może być bardzo trudne, jeśli oprzesz go na czasie i nie masz prawa obalić tego cytatu, chyba że masz w pełni deterministyczne metody.

*) Co ciekawe, prawdopodobnie możesz zwiększyć rzeczywistą przypadkowość, jeśli wybierzesz hardcorową drogę. Wykonaj & 0x01, krok po kroku, i odczekaj chwilę po przeczytaniu każdego bitu. Generowanie danych w ten sposób byłoby absurdalnie długie, ale tak naprawdę twierdziłbym, że można by uznać je za prawie prawdziwie losowe, IIF działa na nie RTOS, a także IFF w każdym „zauważalnym czasie” jest wystarczająco wysoki, aby zapewnić, że podstawa System operacyjny albo przespał się, albo zmienił kontekst na inne zadanie.

Myślę, że odpowiedź, której potrzebujesz, zaczyna się od tego komentarza, który sam udzieliłeś w odpowiedzi innej odpowiedzi:

Wzorzec jest wynikiem gry Java, JVM, systemu operacyjnego, pamięci podręcznej CPU +, dysku twardego, muzyki Trance, którą przesyłałem strumieniowo, która zużywa cykle CPU / RAM i wszystko pomiędzy. Wzorzec powstaje po prostu z jednej linii kodu Java wewnątrz pętli for / next. Znaczna część entropii pochodzi z podstawowych obwodów sprzętowych.

Myślę, że już to zdajesz sobie sprawę: nie użyłeś deterministycznych środków do stworzenia wzorca.

Użyłeś komputera, którego znacząca część jest deterministyczna, ale entropia pochodziła z zewnętrznych niedeterministycznych (lub przynajmniej niedeterministycznych dla wszystkich praktycznych intencji i celów w tej chwili) źródeł: oddziałującego lub zewnętrznego świata z komputerem (oraz, w mniejszym stopniu, wszelkie fizyczne niedoskonałości w sprzęcie komputerowym, które mogą mieć wpływ na czas rzeczy).

Nawiasem mówiąc, jest to duża część tego, jak nowoczesne systemy operacyjne zapełniają generatory liczb losowych, które są dostępne dla programów: poprzez wykorzystanie entropii w interakcjach ze sprzętem i użytkownikiem, które, mamy nadzieję, nie są przewidywalne dla atakującego.

Nawiasem mówiąc, entropia świata zewnętrznego jest w rzeczywistości problemem, który należy rozwiązać do dziś w dobrze zakodowanej kryptografii: komputerach, które których zachowanie jest przewidywalnepodczas rozruchu i podczas uruchamiania, takie jak te z pamięcią tylko do odczytu lub które uruchamiają się z sieci i które mają przewidywalne środowisko sieciowe (niepodłączone do sieci lub obciążenie sieci jest na tyle niskie, że wszystko jest dostarczane w obrębie pewna ilość czasu), które działają na tym samym ograniczonym zestawie oprogramowania z mniej więcej spójnym zachowaniem, mogą rażąco zawyżać entropię, którą uzyskują z tych zakładanych przez siebie nieprzewidywalnych komponentów, i ostatecznie generują znacznie bardziej przewidywalne liczby niż na typowym stanowisku roboczym, które robi dla ciebie wszelkiego rodzaju inne rzeczy (streaming muzyki, synchronizacja z Dropbox, cokolwiek) w tle.

Myślę, że większość odpowiedzi skupia się na tym, czy sprawdzanie ostatnich ośmiu bitów pomiarów czasu w nanosekundach wykonanych w pętli jest dobrym sposobem na uzyskanie tej entropii. To bardzo ważne pytanie, na które należy poprawnie odpowiedzieć, zanim użyjesz metody z przykładu jako schematu generowania liczb losowych w praktyce , ale jest to pytanie odrębne od tego, o co myślę, że pytasz.

Aby dodać do poprzednich odpowiedzi, oto prosty sposób na zastanowienie się nad tym pytaniem.

Chodzi o różnicę między przypadkowym a deterministycznym . Później przyjedziemy do von Neumanna i jego słów.

Losowe liczby

Prawdziwy generator liczb losowych nie miałby żadnego wzoru, nawet nie ukrytego w tle, którego moglibyśmy użyć do przewidzenia następnej liczby, biorąc pod uwagę dotychczasową sekwencję. W idealnym świecie mógłbyś wiedzieć wszystko, co można wiedzieć we wszechświecie fizycznym, a także o systemie, nanosekunda za nanosekundę, a próba przewidzenia następnej liczby nadal byłaby bezużyteczna.

To idealny przypadek - w praktyce osiągamy to poprzez mieszanie ze sobą wielu źródeł, które są „niezłymi przybliżeniami” do przypadkowych lub są naprawdę przypadkowe lub które matematycznie mieszają rzeczy na tyle, że można matematycznie udowodnić, że są bardzo bliskie nieprzewidywalności i brak uprzedzeń do konkretnych liczb lub wzorców.

• „Dobre” źródła to rzeczy podobne do oczekiwania na proces rozpadu radioaktywnego lub inny proces kwantowy, który z natury jest nieprzewidywalny. Wyjście z półprzewodnika wrażliwego na ciepło. Losowy szum w diodzie lub innym materiale elektrycznym. Liczenie fotonów ze słońca.

• W połączeniu z tym możemy również dodać niektóre, które uważamy za „niezłe”, które pomagają, ponieważ nie mają z nimi żadnego połączenia: Oczekiwanie na następne kliknięcie myszą lub pakiet sieciowy. Ostatni kawałek mikrotime przy następnym zapisie pliku. Wyjście funkcji generatora liczb pseudolosowych „znanej, ale dość matematycznie losowej”. Poprzednia entropia z poprzednich zastosowań liczb losowych.

Celem jest uzyskanie liczby, której wciąż nie można przewidzieć , niezależnie od tego, jaki jest wszechświat, który znasz , i jest statystycznie równie prawdopodobne, że to, bez matematycznie wykrywalnego wzorca, stronniczości lub przewidywalności oraz bez korelacji ze zdarzeniem, które mogą być monitorowane i wykorzystywane do prognozowania. (Lub jeśli jest skorelowane ze zdarzeniem, jest to robione w sposób, który sprawia, że ​​połączenie jest niezwykle delikatne, na przykład „cyfra nanosekundowa czasu ostatniego kliknięcia myszy”)

Liczby deterministyczne

Matematycy mogą udowodnić coś o formułach i funkcjach. Można więc udowodnić, że wielokrotnie wywoływana funkcja nie daje żadnego uprzedzenia ani preferencji żadnemu wzorcowi, poza prostym wzorcem „są to wyjścia tej funkcji, jeśli są wielokrotnie wywoływane”.

Na przykład, jeśli wybierzesz liczbę, powiedzmy od 1 do 10 milionów, napisz ją w systemie binarnym i „hasz” wielokrotnie, otrzymasz całkiem losowo wyglądającą sekwencję cyfr. Jest prawie losowy - ale tak naprawdę wcale nie jest przypadkowy. Możesz przewidzieć, biorąc pod uwagę algorytm i dowolny stan, jaka będzie następna liczba.

Nazywamy to „pseudolosowym”, ponieważ wygląda i wydaje się być głównie losowe, nawet jeśli nie jest.

Oto dobry przykład. Pomyśl o tej sekwencji 3-cyfrowych „liczb losowych”: 983, 367, 336, 244, 065, 664, 308, 602, 139, 494, 639, 522, 473, 719, 070, 217. Powiedzmy, że ci powiem Mogę wygenerować milion liczb w ten sam sposób. Następnie możesz przekazać statystykowi, który potwierdzi (powiedzmy), że są one równo rozdzielone lub cokolwiek to może być. Nie ma oczywistego przewidywalnego wzorca. Wyglądają dość losowo, prawda? Ale teraz mówię wam, że tak naprawdę jest

500. cyfra + Pi zgrupowane w 3s.

Nagle, jakkolwiek losowo

cyfry Pi

być może, możesz od razu przewidzieć, że kolejne 2 liczby to 986 i 094.

Żeby było jasne, nie wiem dokładnie, jak losowy

cyfry Pi

są. Zostanie to zbadane, a odpowiedź dobrze znana. Ale chodzi o to: w zasadzie ten sam wniosek dotyczy każdego źródła, które powstaje w wyniku deterministycznego procesu .

Pomiędzy

Pomiędzy nimi znajduje się cała gama „rzeczy, które wyglądają losowo i często są do pewnego stopnia losowe”. Im więcej przypadkowości i prawie przypadkowości można wmieszać, tym mniej podatne jest wyjście na możliwość wykrycia dowolnego wzorca lub przewidywania matematycznego.

Wróć do von Neumanna i twojego pytania

Jak widać, deterministyczne wyniki mogą wyglądać losowo, ale mogą nawet statystycznie być losowo rozmieszczone. Mogą nawet wykorzystywać „tajne” lub szybko zmieniające się dane, o których istnieniu nie mamy realnej nadziei. Ale tak długo, jak to jest deterministyczne, liczby nigdy nie mogą być naprawdę losowe . Mogą być tylko „wystarczająco losowe, aby z przyjemnością zapomnieć o różnicy”.

Takie jest znaczenie cytatu, który podałeś. Proces deterministyczny po prostu nie może dać liczb losowych. Może podawać tylko liczby, które wydają się być i zachowują się jak liczby losowe.

Możemy teraz sformułować twoje pytanie w następujący sposób: „Dane wyjściowe mojego (lub dowolnego współczesnego) komputera mogą wyglądać i zachowywać się całkowicie losowo, czy to znaczy, że cytat von Neumanna jest teraz nieaktualny i niepoprawny?”

Problem jest nadal następujący: nawet jeśli dane wyjściowe komputera mogą wyglądać i zachowywać się losowo, nadal mogą nie być naprawdę przypadkowe . Jeśli jest obliczany tylko deterministycznie, oznacza to, że nie ma nic, co nie byłoby przewidywalnym skutkiem w uzyskaniu następnej liczby (to właśnie oznacza w tym sensie „deterministyczny”). Zaczynamy od niektórych istniejących danych (znanych), stosujemy znany proces (złożony, niechlujny lub cokolwiek innego) i otrzymujemy coś, co wydaje się nową „losową liczbą”. Ale to nie jest przypadkowe, ponieważ proces był deterministyczny.

Jeśli powiesz, że twoja metoda będzie zawierać prawdziwy sprzętowy generator losowy, aby to naprawić (jak losowa liczba wygenerowana z rozpadu radioaktywnego lub szumu w półprzewodniku), wtedy twoja odpowiedź może być losowa - ale twoja metoda z definicji nie jest już deterministyczna , właśnie dlatego, że nie można już przewidzieć wyników (lub efektów) przy danych wejściowych / danych początkowych (przyczynach) .

Von Neumann wygrywa w obie strony, prawie z definicji!