Perché è impossibile produrre numeri veramente casuali?

Si dovrebbe cercare un generatore di numeri pseudo casuali crittograficamente sicuro . La maggior parte dei PRNG sono generatori di congruenza lineare (quindi next number è una funzione lineare di previous number ), quindi se si traccia next number vs previous number si otterrà un grafico di linee parallele. Un CSPRNG non lo farà. Il compromesso è che sono lenti.

Raggruppo i generatori di numeri casuali in 3 categorie :

1. Abbastanza buono per i compiti.
2. Abbastanza buono per scommettere la tua azienda.
3. Abbastanza buono per scommettere il tuo paese.

Why is it impossible to produce truly random numbers in any deterministic device ?

Un dispositivo deterministico produrrà sempre lo stesso risultato quando vengono date le stesse condizioni di partenza e gli stessi input - questo è ciò che significa essere deterministic . "Il numero veramente casuale" è più di un punto di vista filosofico, poiché ciò che significa essere random è il punto cruciale dell'osservazione dell'ombelico filosofico (la gente non è nemmeno certa se il decadimento atomico è casuale o segue qualche schema che possiamo solo " t capire ancora). Un generatore di numeri casuali protetto da crittografia sta per prendere una fonte esterna di entropia per rendere il dispositivo non deterministico.

La vera casualità implica il non determinismo. Se è deterministico, può essere previsto con precisione (questo è il significato del determinismo); se può essere previsto, non è casuale.

La cosa migliore che si può ottenere da un generatore di numeri pseudo-casuali deterministico è un flusso di numeri che ha un ciclo molto lungo (non ripetibile è impossibile a meno che il dispositivo RNG abbia spazio illimitato) che, per la lunghezza del ciclo , produce un numero di stream che soddisfa tutte le altre proprietà di una sequenza casuale (una distribuzione uniforme dei valori è la più interessante).

Per risolvere questo problema, molti moderni Unix e Unix-like hanno kernel RNG che usano sorgenti di rumore fisico per generare casualità.

Un altro approccio comune è quello di prendere il tempo corrente come seme per un RNG deterministico ( srand(time(NULL)); in C); crittograficamente parlando, questo è inutile, dal momento che il tempo corrente non è un segreto, ma per cose come simulazioni fisiche o videogiochi, è abbastanza buono.

Il secondo capitolo del libro Simulazione di eventi discreti: un primo corso di Lawrence Leemis offre una fantastica introduzione ai generatori di numeri casuali (o più precisamente, generatori di numeri psuedo-casuali).

Un estratto del suo libro lo spiega bene secondo me:

Historically three types of random number generators have been advocated for computational applications: (a) 1950's-style table look-up generators like, for example, the RAND corporation table of a million random digits; (b) hardware generators like, for example, thermal "white noise" devices; and (c) algorithmic (software) generators. Of these three types, only algorithmic generators have achieved widespread acceptance. The reason for this is that only algorithmic generators have the potential to satisfy all of the following generally well-accepted random number generation criteria. A generator should be:

• random - able to produce output that passes all reasonable statistical tests of randomness;
• controllable - able to reproduce its output, if desired;
• portable - able to produce the same output on a wide variety of computer systems;
• efficient - fast, with minimal computer resource requirements;
• documented - theoretically analyzed and extensively tested.

Quindi, mentre potrebbe essere possibile utilizzare un generatore di rumore bianco per ottenere numeri casuali "migliori", non hanno ottenuto l'approvazione perché non seguono la maggior parte dei criteri sopra indicati.

Ti consiglierei di mettere le mani su una copia di quel libro (o qualcosa di simile). Capire esattamente come il lavoro di PRNG ti aiuterà sicuramente nei tuoi sforzi.

Perché è necessario scrivere codice per generare numeri casuali e il codice è NON casuale. (È deterministico)

Quindi finisci con un "valore / i di semi" che viene selezionato su "Random" (di solito il timestamp corrente), quindi usalo in un algoritmo per iniziare a generare numeri. Ma l'intero set è basato sul valore di seme originale!

Quindi se esegui di nuovo il tuo codice con lo stesso esatto valore di semi, otterrai lo stesso SET di numeri! Come può una persona ragionevole chiamarla casualmente? Ma sicuramente LOOK random.

Per renderli unici, dopo aver generato un numero, controlla semplicemente se hai già quel numero, se lo fai, buttalo via e generane uno nuovo.

Poiché stai generando numeri casuali, dovresti aspettarti che i valori generati siano non univoci. Questa è una proprietà di casualità - non si può dire che una sequenza di numeri veramente casuali (o anche pseudo-casuali) sia univoca, poiché tale requisito consentirebbe di prevedere il valore finale nell'intervallo, oltre a modificare la probabilità di tutti i numeri non scelti ogni volta che ne viene selezionato uno nuovo.

Ho una definizione molto semplice di Pseudo Random :

Troppe variabili sconosciute da prevedere.

Ho anche una semplice definizione di True Random :

Variabili sconosciute infinite.

Il problema con un computer è che conosce sempre TUTTE le variabili. Il numero casuale è semplicemente una funzione matematica di alcuni valore seme .
Il meglio che possiamo fare è dare al computer un valore seme pseudo-casuale, che di solito è basato su una variabile che non possiamo prevedere (come l'ora esatta).

Anche se un computer non è assolutamente in grado di creare un numero casuale, è utile introdurre troppe variabili da prevedere!

La generazione di numeri veramente casuali nel software non è effettivamente possibile come altri hanno sottolineato, tuttavia è possibile con l'hardware costruire un dispositivo che può generare numeri veramente casuali *. Ci sono parecchi esempi di questo su internet, e ci sono una varietà di metodi usati, dalla lettura del tempo tra le zecche sul contatore Geiger al campionamento del rumore bianco (principalmente la radiazione di fondo dell'universo) di un ricevitore non sintonizzato. Io stesso ho ne ho costruito alcuni usando un alcuni dei metodi disponibili.

* Qualsiasi buon geek della fisica farà notare che dato il modo in cui l'universo funziona, nessuno di questi è ipertecnologico veramente casuale, ma non esiste un modo ragionevole per predire il i risultati sono sufficienti per il fine di questa discussione.

Non è possibile produrre un numero casuale senza un hardware speciale. Nel mio primo anno, un paio di compagni di classe e io abbiamo proposto un generatore di numeri casuali che ha fondamentalmente un ricevitore AM e sintonizzato su 4 canali diversi, ottenere l'input in un convertitore da A a D e aggiungerli tutti (modulo il numero massimo). Poiché la combinazione di input analogici da qualsiasi numero arbitrario di stazioni è casuale e potremmo produrre un numero elevato di numeri casuali dal convertitore A2D, abbiamo proposto che questo potrebbe essere un buon generatore. Naturalmente, anche questo non è veramente casuale in senso filosofico, anche se per scopi pratici potrebbe funzionare.

Il determinismo è essenzialmente una funzione. Ricorda da Algebra che una funzione è una corrispondenza tra un dominio e un intervallo tale che ogni membro del dominio corrisponde esattamente a un membro dell'intervallo.

Quindi se f (x) = z, f (x)! = y a meno che y sia z. Questa è una funzione. Immagina JavaScript:

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

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

Non importa quante volte chiami Add(2,3) tornerà sempre 5. In altre parole, Add () è una funzione deterministica.

I fattori esterni possono rendere Add comportarsi in modo non deterministico. Ad esempio, se si introduce il multithreading nell'equazione. L'input umano causa anche non determinismo.

Ora, è qui che le cose si fanno interessanti.

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

Nota Von Neumann afferma, "metodi aritmetici per produrre [...]". Non si tratta di input umani, concorrenza, velocità del vento del campione lette da uno strumento preciso o altri modi non algoritmici di produrre un input casuale in una funzione deterministica.

Questo semplicemente afferma che una funzione o un sistema di funzioni non diventerà improvvisamente non deterministico. In altre parole, Aggiungi (2,3) non restituirà in qualche modo 6 o qualsiasi cosa diversa da 5 dati gli stessi input . Questo è impossibile.

L'autore delle citazioni fa un ulteriore passo in avanti.

The best we can hope for are pseudo-random numbers, a stream of numbers that appear as if they were generated randomly.

Il contesto è definito in precedenza come "su qualsiasi dispositivo deterministico". Potrei concludere la discussione qui. Ma, cosa succede se cambiamo il contesto introducendo un nuovo elemento nel sistema? Un elemento non deterministico aggiunto come input rende il sistema un sistema non deterministico. Sebbene, rimuovendo l'elemento non deterministico, ci si riduca a un sistema deterministico. Se possiamo in qualche modo tracciare o riprodurre in altro modo gli input, possiamo riprodurre un risultato. Ma questo intero paragrafo è tangente a quello che sta dicendo l'autore. Ricorda il contesto.

Si potrebbe discutere sul significato del non-determinismo. Ancora una volta, tangetenial. Ricorda il contesto.

Quindi ha ragione. Su qualsiasi dispositivo deterministico è impossibile per un sistema deterministico produrre un risultato casuale reale.