Esistono generatori di numeri casuali senza stato?

Question

C'è una differenza tra generare più numeri usando un singolo generatore di numeri casuali (RNG) rispetto a generare un numero per generatore e scartarlo? Entrambe le implementazioni generano numeri ugualmente casuali? C'è una differenza tra i RNG normali e i RNG sicuri per questo?

Ho un'applicazione web che dovrebbe generare un elenco di numeri casuali per conto dei clienti. Cioè, i numeri dovrebbero apparire casuali dal punto di vista di ciascun cliente. Questo significa che devo conservare un RNG casuale separato per sessione client? O posso condividere un singolo RNG in tutte le sessioni? Oppure posso creare e scartare un RNG in base alla richiesta?

AGGIORNAMENTO : questa domanda è correlata a Anche un sottoinsieme di una sequenza casuale è casuale?

Answer 1

Un generatore di numeri casuali ha uno stato, che in realtà è una funzione necessaria. Il prossimo "casuale" numero è una funzione del numero precedente e del seme / stato. I puristi li chiamano generatori di numeri pseudo-casuali. I numeri supereranno i test statistici per casualità, ma non sono - in realtà - casuali.

La sequenza di valori casuali è finita e si ripete.

Pensa a un generatore di numeri casuali come a mescolare una raccolta di numeri e poi distribuirli in un ordine casuale. Il seme viene utilizzato per "mescolare" i numeri. Una volta impostato il seme, la sequenza di numeri è fissa e molto difficile da prevedere. Alcuni semi si ripeteranno prima di altri.

La maggior parte dei generatori ha un periodo abbastanza lungo che nessuno noterà la sua ripetizione. Un generatore di numeri casuali a 48 bit produrrà diverse centinaia di miliardi di numeri casuali prima che si ripeta - con (AFAIK) qualsiasi valore di seed a 32 bit.

Un generatore genererà solo valori casuali quando gli dai un singolo seme e gli fai vomitare valori. Se cambi seed, i numeri generati con il nuovo valore seed potrebbero non apparire casuali rispetto ai valori generati dal seed precedente: tutte le scommesse sono disattivate quando cambi seed. Quindi non.

Un approccio valido è quello di avere un generatore e "trattare". i numeri intorno ai tuoi vari clienti. Non scherzare con la creazione e l'eliminazione di generatori. Non scherzare con il cambio dei semi.

Soprattutto, non provare mai a scrivere il tuo generatore di numeri casuali. I generatori integrati nella maggior parte delle librerie di lingue sono davvero buoni. Soprattutto quelli moderni che usano più di 32 bit.

Alcune distribuzioni Linux hanno un dispositivo / dev / random e / dev / urandom . Puoi leggerli una volta per eseguire il seeding del generatore di numeri casuali della tua applicazione. Questi hanno valori più o meno casuali, ma funzionano per "raccogliere il rumore" da eventi di sistema casuali. Usali con parsimonia in modo che ci siano molti eventi casuali tra gli usi.

Answer 2

Consiglierei di utilizzare più volte un singolo generatore. Per quanto ne so, tutti i generatori hanno uno stato. Quando si semina un generatore, si imposta il suo stato su qualcosa in base al seme. Se continui a generarne di nuovi, è probabile che i semi che scegli non saranno casuali come i numeri generati utilizzando un solo generatore.

Questo è particolarmente vero con la maggior parte dei generatori che ho usato, che usano come seme il tempo corrente in millisecondi.

Answer 3

Sono possibili generatori di numeri casuali basati su hardware, vero [1], ma non banali e spesso hanno bassi tassi medi. La disponibilità può anche essere un problema [2]. Googling per "rumore di sparo" o "decadimento radioattivo" in combinazione con "generatore di numeri casuali" dovrebbe restituire alcuni hit.

Non è necessario che questi sistemi mantengano lo stato. Probabilmente non quello che stavi cercando.

Come notato da altri, i sistemi software sono solo pseudo casuali e devono mantenere lo stato.

Un compromesso consiste nell'utilizzare un RNG basato su hardware per fornire un pool di entropia (stato memorizzato) reso disponibile per eseguire il seeding di un PRNG. Questo viene fatto in modo abbastanza esplicito nell'implementazione di Linux di / dev / random [3] e / dev / urandom [4].

Questi sono alcuni argomenti su quanto casuali siano gli input predefiniti nel pool di entropia / dev / random.

---

Note:

1. modulo eventuali problemi con la nostra comprensione della fisica
2. perché stai aspettando un processo casuale
3. / dev / random offre l'accesso diretto al pool di entropia generato da varie fonti ritenute realmente o quasi casuali e si blocca quando l'entropia è esaurita
4. / dev / urandom è come / dev / random, ma quando l'entopia è esaurita viene impiegato un hash crittografico che rende efficacemente il pool di entropia un PRNG con stato

Answer 4

Se crei un RNG e generi un singolo numero casuale da esso, quindi scarti l'RNG, il numero generato è casuale solo come il seme utilizzato per avviare l'RNG.

Sarebbe molto meglio creare un singolo RNG e trarne molti numeri.

Answer 5

Come la gente ha già detto, è molto meglio seminare il PRNG una volta e riutilizzarlo. Un PRNG sicuro è semplicemente idoneo per applicazioni crittografiche. L'unico modo in cui il re-seeding ogni volta darà risultati ragionevolmente casuali è da dove proviene un "mondo reale" realmente casuale sorgente - ovvero hardware specializzato. Anche allora, è possibile che la fonte sia distorta e teoricamente sarebbe comunque meglio usare lo stesso PRNG.

Answer 6

Normalmente seminare un nuovo stato richiede del tempo per un PRNG serio, e crearne di nuovi ogni volta non sarà di grande aiuto. L'unico caso che mi viene in mente dove potresti desiderare più di un PRNG è per sistemi diversi, ad esempio in un gioco da casinò hai un generatore per mescolare le carte e uno separato per generare commenti fatti dai personaggi di controllo del computer, in questo modo REALMENTE dedicato gli utenti non possono indovinare i risultati in base al comportamento dei personaggi.

Una buona soluzione per il seeding è usare questo (Random.org) , forniscono casualmente numeri generati dal rumore atmosferico gratuitamente. Potrebbe essere una fonte migliore per il seeding rispetto all'uso del tempo.

Modifica: nel tuo caso, utilizzerei sicuramente un PRNG per client, se non altro per buoni standard di programmazione. Tuttavia, se condividi un PRNG tra i clienti, fornirai comunque valori pseudo-casuali a ciascuno, di una qualità pari alla qualità del tuo PRNG. Quindi questa è un'opzione praticabile ma sembra una cattiva politica per la programmazione

Answer 7

Vale la pena ricordare che Haskell è un linguaggio che tenta di eliminare completamente lo stato mutevole. Al fine di conciliare questo obiettivo con requisiti rigidi come IO (che richiede una qualche forma di mutabilità), le monadi devono essere utilizzate per eseguire il thread dello stato da un calcolo al successivo. In questo modo, Haskell implementa il suo generatore di numeri pseudo-casuale. A rigor di termini, generare numeri casuali è un'operazione intrinsecamente piena di stato, ma Haskell è in grado di nascondere questo fatto spostando lo stato "mutazione". nell'operazione bind ( > > = ).

Probabilmente sembra un po 'astratto, e in realtà non risponde completamente alla tua domanda, ma penso che sia ancora applicabile. Da un punto di vista teorico, è impossibile lavorare con un RNG senza coinvolgere lo stato. Indipendentemente da ciò, ci sono tecniche che possono essere utilizzate per mitigare questa interazione e farla apparire come se l'intera operazione fosse di natura apolide.

Answer 8

In genere è meglio creare un singolo PRNG e ricavarne più valori. La creazione di più istanze significa che è necessario assicurarsi che i seed per le istanze siano garantiti univoci, il che richiederà l'incorporazione di informazioni specifiche dell'istanza.

A parte questo, ci sono meglio " true " Generatori di numeri casuali, ma di solito richiedono hardware specializzato che fa cose come derivare dati casuali dalla variazione del segnale elettrico all'interno del computer. A meno che tu non sia davvero preoccupato, direi che i generatori di numeri casuali pseudo integrati nelle librerie di lingue e / o nel sistema operativo sono probabilmente sufficienti, a condizione che il tuo valore seed non sia facilmente prevedibile.

Answer 9

L'uso di un PRNG sicuro dipende dalla tua applicazione. A cosa servono i numeri casuali? Se sono qualcosa di valore reale (ad es. Qualcosa di crittograficamente correlato), non vorresti usare niente di meno.

I PRNG sicuri sono molto più lenti e possono richiedere che le librerie eseguano operazioni di precisione arbitraria e test di primalità, ecc. ecc.

Answer 10

Bene, fintanto che vengono seminati in modo diverso ogni volta che vengono creati, quindi no, non penso che ci sarebbe alcuna differenza; tuttavia, se dipendesse da qualcosa come il tempo, probabilmente sarebbero non uniformi, a causa del seme distorto.