generatore pseudo-casuale
generatore pseudo-casuale
Una sequenza C di elementi tratti da un insieme S è casuale se l’apparizione di ciascun elemento non può essere predetta con probabilità diversa da quella che gli deriva dalla sua frequenza in S. Se per es., S è l’insieme delle dieci cifre decimali, ciascuna cifra ha probabilità pari a 1/10 di apparire in C e la prossima apparizione di una data cifra non è prevedibile con probabilità diversa da 1/10. Una sequenza pseudo-casuale P ha proprietà statistiche complessive simili a quelle delle sequenze casuali ma è generata da un algoritmo detto generatore pseudo-casuale: i suoi elementi, determinati dal valore di un parametro iniziale dell’algoritmo detto seme, sono quindi totalmente prevedibili. I test statistici di valutazione tendono ad accertare l’esistenza nella sequenza P di alcune proprietà della C, come la frequenza delle apparizioni in P degli elementi dell’insieme S e la distanza tra essi. I primi generatori pseudo-casuali interessanti furono ideati negli anni Quaranta del secolo scorso per la simulazione di processi di varia natura mediante metodi matematici Monte Carlo. Un classico generatore di interi positivi che supera con successo i test statistici standard è il generatore lineare che, a partire da un seme casuale x0, produce una sequenza di interi x1, x2,x3… compresi tra 0 e m−1, calcolati con la formula xi=a xi−1+b (mod m), ove a,b,m sono scelti con opportune regole. Oltre che per la simulazione di processi, i generatori pseudo-casuali sono oggi impiegati nell’esecuzione di algoritmi randomizzati che eseguono al loro interno scelte casuali per ottenere in tempi brevi risultati esatti con altissima probabilità, e in diverse applicazioni crittografiche. Queste ultime richiedono generatori particolarmente sofisticati, detti crittograficamente sicuri, in cui la non prevedibilità degli elementi nella sequenza P, impossibile da imporre, è interpretata come pratica impossibilità di eseguire tale previsione poiché il tempo necessario è espresso da una funzione esponenziale nella dimensione degli elementi generati.