Un numero pseudocasuale è un numero speciale generato da un generatore speciale. Il Deterministic Random Bit Generator (PRNG), noto anche come Deterministic Random Bit Generator (DRBG), è un algoritmo per generare una sequenza di numeri le cui proprietà si avvicinano alle caratteristiche delle sequenze di numeri casuali. La sequenza PRNG generata non è veramente casuale, poiché è interamente determinata da un valore seme chiamato seme PRNG, che può includere valori veramente casuali. Sebbene le sequenze più vicine al casuale possano essere generate utilizzando generatori di numeri casuali hardware, i generatori di numeri pseudo-casuali sono importanti in pratica per la velocità di generazione dei numeri e la loro riproducibilità.
Applicazione
I PRNG sono fondamentali per applicazioni come la simulazione (ad esempio per Monte Carlo), i giochi elettronici (ad esempio per la generazione procedurale) e la crittografia. Le applicazioni crittografiche richiedono che l'outputi dati non erano prevedibili da informazioni precedenti. Sono necessari algoritmi più complessi che non ereditino la linearità dei semplici PRNG.
Termini e condizioni
Buone proprietà statistiche sono un requisito fondamentale per ottenere un PRNG. In generale, è necessaria un'attenta analisi matematica per essere sicuri che l'RNG generi numeri abbastanza vicini alla casualità da essere appropriati per l'uso previsto.
John von Neumann ha messo in guardia dall'interpretare erroneamente il PRNG come un generatore veramente casuale e ha scherzato sul fatto che "Chiunque consideri metodi aritmetici per generare numeri casuali è certamente in uno stato di peccato."
Usa
PRNG può essere lanciato da uno stato iniziale arbitrario. Genererà sempre la stessa sequenza quando inizializzato con questo stato. Il periodo PRNG è definito come segue: massimo su tutti gli stati iniziali della lunghezza del prefisso della sequenza non ripetuta. Il periodo è limitato dal numero di stati, solitamente misurato in bit. Poiché la lunghezza del periodo potenzialmente raddoppia con ogni bit di "stato" aggiunto, è facile creare PRNG con periodi sufficientemente grandi per molte applicazioni pratiche.
Se lo stato interno del PRNG contiene n bit, il suo periodo non può essere superiore a 2n risultati, è molto più breve. Per alcuni PRNG, la durata può essere calcolata senza bypassare l'intero periodo. I registri di spostamento del feedback lineare (LFSR) sono in generesono scelti in modo da avere periodi uguali a 2n − 1.
I generatori congruenti lineari hanno periodi che possono essere calcolati utilizzando il factoring. Sebbene il PPP ripeterà i suoi risultati dopo aver raggiunto la fine del periodo, un risultato ripetuto non significa che la fine del periodo è stata raggiunta, poiché il suo stato interno può essere maggiore dell'output; questo è particolarmente evidente per i PRNG con uscita a bit singolo.
Possibili errori
Gli errori rilevati da PRNG difettosi vanno da sottili (e sconosciuti) a ovvi. Un esempio è l'algoritmo dei numeri casuali RANDU, utilizzato da decenni sui mainframe. Era un grave difetto, ma la sua inadeguatezza è passata inosservata per un lungo periodo di tempo.
In molte aree, gli studi di ricerca che hanno utilizzato la selezione casuale, le simulazioni Monte Carlo o altri metodi basati sull'RNG sono molto meno affidabili di quanto potrebbero essere il risultato di GNPG di scarsa qualità. Ancora oggi, a volte è necessaria cautela, come dimostra l'avvertimento nell'Enciclopedia internazionale di scienze statistiche (2010).
Case study di successo
A titolo illustrativo, considera il linguaggio di programmazione Java ampiamente utilizzato. A partire dal 2017, Java si affida ancora al generatore congruenziale lineare (LCG) per il suo PRNG.
Cronologia
Il primo PRNG per evitare seri problemi e continuare a funzionare abbastanza velocemente,era il Mersenne Twister (discusso di seguito), pubblicato nel 1998. Da allora sono stati sviluppati altri PRNG di alta qualità.
Ma la storia dei numeri pseudocasuali non finisce qui. Nella seconda metà del 20° secolo, la classe standard di algoritmi utilizzati per i PRNG includeva generatori congruenti lineari. La qualità dell'LCG era nota per essere inadeguata, ma non erano disponibili metodi migliori. Press et al (2007) hanno descritto il risultato come segue: "Se tutti i documenti scientifici i cui risultati sono in dubbio a causa di [LCG e correlati] scomparissero dagli scaffali delle biblioteche, ci sarebbe uno spazio vuoto delle dimensioni del tuo pugno su ogni scaffale."
Il principale risultato nella creazione di generatori pseudo-casuali è stata l'introduzione di metodi basati sulla ricorrente lineare in un campo a due elementi; tali oscillatori sono accoppiati a registri a scorrimento a retroazione lineare. Sono serviti come base per l'invenzione di sensori numerici pseudo-casuali.
In particolare, l'invenzione del 1997 di Mersen Twister ha evitato molti dei problemi con i generatori precedenti. Il Mersenne Twister ha un periodo di 219937-1 iterazioni (≈4,3 × 106001). È stato dimostrato che è distribuito uniformemente in (fino a) 623 dimensioni (per valori a 32 bit) e al momento della sua introduzione era più veloce di altri generatori di suoni statisticamente che producono sequenze di numeri pseudo-casuali.
Nel 2003, George Marsaglia ha introdotto una famiglia di generatori xorshift anch'essi basati sulla ripetizione lineare. Questi generatori sono estremamentesono veloci e, combinati con un'operazione non lineare, superano rigorosi test statistici.
Nel 2006 è stata sviluppata la famiglia di generatori WELL. I generatori BENE in un certo senso migliorano la qualità di Twister Mersenne, che ha uno spazio degli stati troppo ampio e un recupero molto lento da essi, generando numeri pseudo-casuali con molti zeri.
Crittografia
PRNG adatto per applicazioni crittografiche è chiamato PRNG crittograficamente sicuro (CSPRNG). Il requisito per un CSPRNG è che un utente malintenzionato che non conosce il seme abbia solo un vantaggio marginale nel distinguere la sequenza di output del generatore da una sequenza casuale. In altre parole, mentre un PRNG è richiesto solo per superare determinati test statistici, un CSPRNG deve superare tutti i test statistici limitati al tempo polinomiale nella dimensione del seme.
Sebbene la dimostrazione di questa proprietà sia al di là dell'attuale livello della teoria della complessità computazionale, è possibile fornire una forte evidenza riducendo il CSPRNG a un problema considerato difficile, come la fattorizzazione di interi. In generale, potrebbero essere necessari anni di revisione prima che un algoritmo possa essere certificato come CSPRNG.
È stato dimostrato che è probabile che l'NSA abbia inserito una backdoor asimmetrica nel generatore di numeri pseudocasuali Dual_EC_DRBG certificato dal NIST.
Algoritmi pseudocasualinumeri
La maggior parte degli algoritmi PRNG produce sequenze che sono distribuite uniformemente da uno qualsiasi dei numerosi test. Questa è una domanda aperta. È uno dei punti centrali nella teoria e nella pratica della crittografia: c'è un modo per distinguere l'output di un PRNG di alta qualità da una sequenza veramente casuale? In questa impostazione, il risolutore sa che è stato utilizzato un algoritmo PRNG noto (ma non lo stato con cui è stato inizializzato) oppure è stato utilizzato un algoritmo veramente casuale. Deve distinguerli.
La sicurezza della maggior parte degli algoritmi e dei protocolli crittografici che utilizzano i PRNG si basa sul presupposto che è impossibile distinguere tra l'uso di un PRNG adatto e l'uso di una sequenza veramente casuale. Gli esempi più semplici di questa dipendenza sono i cifrari a flusso, che il più delle volte funzionano omettendo o inviando il messaggio in chiaro con un output PRNG, producendo il testo cifrato. La progettazione di PRNG crittograficamente adeguati è estremamente difficile in quanto devono soddisfare criteri aggiuntivi. La dimensione del suo periodo è un fattore importante nell'idoneità crittografica di un PRNG, ma non l'unico.
Uno dei primi PRNG per computer proposto da John von Neumann nel 1946 è noto come metodo dei quadrati medi. L'algoritmo è il seguente: prendi un numero qualsiasi, quadralo, rimuovi le cifre centrali del numero risultante come "numero casuale", quindi usa questo numero come numero iniziale per l'iterazione successiva. Ad esempio, la quadratura del numero 1111 dà1234321, che può essere scritto come 01234321, un numero di 8 cifre è il quadrato di un numero di 4 cifre. Questo dà 2343 come numero "casuale". Il risultato della ripetizione di questa procedura è 4896 e così via. Von Neumann usava numeri a 10 cifre, ma il procedimento era lo stesso.
Svantaggi della "piazza di mezzo"
Il problema con il metodo del "quadrato medio" è che tutte le sequenze alla fine si ripetono, alcune molto rapidamente, ad esempio: 0000. Von Neumann lo sapeva, ma trovò un approccio sufficiente per i suoi scopi e temeva che il Le "correzioni" matematiche nasconderebbero semplicemente gli errori invece di rimuoverli.
Von Neumann ha riscontrato che i generatori di numeri casuali e pseudocasuali hardware non sono adatti: se non registrano l'output generato, non possono essere controllati per errori in un secondo momento. Se dovessero annotare i loro risultati, esaurirebbero la memoria disponibile limitata del computer e quindi la capacità del computer di leggere e scrivere numeri. Se i numeri fossero scritti sulle carte, ci vorrebbe molto più tempo per scrivere e leggere. Sul computer ENIAC ha utilizzato il metodo del "quadrato medio" ed ha eseguito il processo per ottenere numeri pseudocasuali centinaia di volte più velocemente rispetto alla lettura di numeri da schede perforate.
Il quadrato medio da allora è stato sostituito da generatori più complessi.
Metodo innovativo
Una recente innovazione consiste nel combinare il quadrato medio con la sequenza di Weil. Questo metodo garantisce prodotti di alta qualità all'internolungo periodo. Aiuta a ottenere le migliori formule numeriche pseudocasuali.
