Generatore di numeri pseudo-casuali
Da Wikipedia, l'enciclopedia libera.
Un generatore di numeri pseudo-casuali (PRNG, dall'inglese Pseudo Random Number Generator) è un algoritmo che genera una successione di numeri, i cui elementi sono approssimativamente indipendenti l'uno dall'altro.
Per esempio, se abbiamo una sequenza di numeri 1,2,3,4,5,6,7,8,9 sappiamo individuare un algoritmo che li possa rappresentare, che in questo caso è identificato dal sommare 1 al precedente. Se abbiamo una sequenza di numeri 1,7,9,10,8,11,2,5,3,4,6,12 non siamo sicuri che questa possa essere generata dal caso o da un generatore. In quest'ultimo caso esiste un generatore modulo 13 che ci permette di dare una parvenza di casualità ed una ripetibilità della sequenza.
I risultati forniti da un generatore di numeri pseudo-casuali non sono veramente casuali, essi approssimano solo alcune delle proprietà dei numeri casuali. Mentre i numeri "veramente" casuali possono essere generati usando generatori hardware di numeri casuali, i numeri pseudocasuali sono una parte critica della moderna scienza computazionale, dalla crittografia al metodo Monte Carlo per simulare i sistemi fisici. Un'attenta analisi matematica è richiesta per assicurare che i numeri generati siano sufficientemente "casuali". Robert R. Coveyou del Oak Ridge National Laboratory ha intitolato un articolo, "La generazione dei numeri casuali è troppo importante per essere lasciata al caso."
La maggioranza di tali algoritmi tenta di produrre campioni che sono uniformemente distribuiti. Comuni classi di algoritmi sono generatori congruenti lineari, generatori di Fibonacci ritardati, registri a scorrimento con retroazione lineare e registri a scorrimento con retroazione generalizzata.
Uno dei generatori migliori e più veloci, adatto per l'uso scientifico (compreso il metodo Monte Carlo), è Mersenne Twister: ha un periodo di 219937-1 e garantisce l'equidistribuzione in 623 dimensioni; inoltre è addirittura più veloce del semplicissimo (ma pessimo) generatore LCG interno del linguaggio C (la funzione rand()).
Per l'utilizzo in crittografia è necessario utilizzare generatori di numeri pseudo-casuali crittograficamente sicuri quali Fortuna o Blum Blum Shub.
