Generatori di numeri casuali: la loro importanza in ambito informatico

Operazioni come il lancio di una moneta fisica o vedere dove si ferma una pallina della roulette sono generalmente considerati come esempi di casualità vera.
John von Neumann, famoso matematico, fisico, informatico e filosofo (1903-1957) che ha fornito le basi matematiche per lo sviluppo dei computer (famosa la sua omonima “architettura“, diceva che “chiunque consideri i metodi aritmetici per produrre cifre casuali è in uno stato di peccato“. Ecco perché lanciare una moneta viene da molti citato come un esempio di casualità naturale.
In realtà è dimostrabile che conoscendo l’ambiente e gli strumenti utilizzati, quindi avendo a disposizione una cronologia puntuale degli eventi passati, sia possibile prevedere il percorso di una pallina della roulette o l’uscita di “testa” o “croce” in seguito al lancio di una moneta.

I generatori di numeri casuali “veri” utilizzano processi fisici imprevedibili come il rumore termico, il decadimento radioattivo o la turbolenza atmosferica.
Probabilmente, comunque, osservando gli accadimenti da una prospettiva veramente onnisciente nulla, nemmeno il mondo fisico, è veramente casuale perché gli accadimenti che via via si registrano sono figli di una catena di eventi precedenti.
Per la maggior parte degli eventi considerati come casuali è impossibile guadagnare una simile prospettiva onnisciente che è quindi qualcosa di irrealizzabile e di fatto impossibile.

Perché si parla di generatori di numeri pseudocasuali

In informatica, e lo abbiamo osservato in tanti articoli, si parla infatti di generazione di numeri pseudocasuali: non è possibile generare numeri veramente casuali utilizzando un computer o una formula matematica deterministica.

I numeri generati da un computer sono basati su un algoritmo matematico e su un insieme di valori di input noti come “seed“. Anche se questi numeri sembrano casuali, se si conoscono l’algoritmo e il seed (un po’ come la chiave crittografica nella crittografia) utilizzati, è possibile riprodurre gli stessi numeri. Non conoscendo il seed,l’output risulta molto difficile da prevedere.

Proprio per questo motivo, i numeri generati da un computer vengono chiamati “pseudocasuali”: essi sembrano casuali ma in realtà sono generati in modo deterministico.
La difficoltà nella previsione dell’output dipende dai dettagli di funzionamento del generatore: in alcuni casi può essere molto complessa, in altri (ad esempio a causa di “debolezze” dell’algoritmo stesso) addirittura banale.

La generazione di numeri pseudocasuali viene utilizzata in molti contesti, come ad esempio nella crittografia, nelle attività di generazione delle password, nella simulazione di fenomeni fisici, nella progettazione di giochi e applicazioni di ogni genere.
La crittografia moderna, tecnologia utilizzata anche per proteggere le transazioni online, si basa sulla complessità nel fare previsioni sul comportamento del generatore di numeri casuali.

Si supponga di confrontarsi con un gioco per computer che si basa soltanto sulla fortuna: esso include ovviamente un generatore di numeri casuali. Ecco, quel generatore potrebbe essere stato sviluppato affinché i gestori del sistema possano sapere con certezza se l’utente vincerà o meno (acquisizione della prospettiva onnisciente cui facevamo riferimento in precedenza…). Al contrario, per molti fenomeni naturali, è impossibile per chiunque avere una prospettiva onnisciente sugli accadimenti.

Codebook e generazione di numeri pseudocasuali

Parlando di generazione di numeri pseudocasuali, un codebook è un insieme di valori o di sequenze di valori predefinite utilizzate come punto di partenza per la generazione di numeri pseudocasuali.

Un codebook è una sorta di “libro delle regole” contenente una lista di numeri o sequenze di numeri selezionati in modo che, utilizzati in combinazione con un algoritmo deterministico, producano numeri che sembrano casuali. Il generatore sceglie una sequenza dal codebook come seed e poi utilizza un algoritmo matematico per trasformare il seed in una sequenza di numeri,

Un buon codebook deve contenere valori sufficientemente complessi e diversificati per garantire che la sequenza generata sia imprevedibile. Deve inoltre essere grande e contenere pagine con variazioni significative dei dati per impedire che le sequenze generate diventino prevedibili.

Bit e periodo

In un generatore di numeri pseudocasuali, i “bit” si riferiscono alla quantità di informazioni che viene utilizzata per rappresentare ciascun numero pseudocasuale generato: date un’occhiata al nostro articolo sul codice binario. Se un generatore utilizza 32 bit, significa che ogni numero pseudocasuale è rappresentato utilizzando 32 “unità” di informazione.

Il periodo si riferisce invece alla lunghezza della sequenza di numeri che il generatore è in grado di generare prima di ripetere una sequenza identica. Un generatore di numeri pseudocasuali con un periodo più lungo può quindi generare una sequenza di numeri pseudocasuali più lunga prima che inizi a ripetere una sequenza. Questo parametro dipende da come è internamente dimensionato il generatore.

Un generatore a 32 bit con un periodo di 2³² può essere paragonato a un codebook con una dimensione pari a 16 GB.
Un generatore a 32 bit con un periodo di 2⁶⁴ sarebbe come se utilizzasse un vero libro tale da richiedere, per essere stampato, della cellulosa derivabile da tutte le foreste disponibili sulla Terra.

Nel caso dei generatori di numeri casuali che utilizziamo, la sequenza ovvero il codebook è nota: per evitare previsioni è necessario mantenere il segreto sulla pagina del libro alla quale sta attingendo il generatore. Se la sequenza è abbastanza grande è impossibile capire quali numeri verranno dopo.

Abbiamo preso il caso della sicurezza dell’algoritmo RSA per dire che alcune implementazioni si servono di generatori di numeri primi pseudocasuali “deboli”. La sicurezza dell’algoritmo crittografico si basa per larga parte sui numeri primi generati: se non sono sufficientemente casuali è molto più facile per gli attaccanti fattorizzarli e rompere la crittografia. Ecco perché il generatore di numeri pseudocasuali deve essere crittograficamente sicuro.

Che cos’è lo schema PCG, Permuted Congruential Generator

Lo schema di generazione PCG (Permuted Congruential Generator) è un algoritmo per la generazione di numeri pseudocasuali che combina un generatore congruenziale lineare (LCG) con una funzione di permutazione.

PCG utilizza una formula matematica per produrre una sequenza di numeri che sembrano casuali, ma che in realtà sono deterministici, poiché – come abbiamo visto in precedenza – derivano comunque da un seed.

Il PCG è stato presentato nel 2014 da Melissa O’Neill ed è diventato uno dei generatori di numeri pseudocasuali più popolari e consigliati per le applicazioni informatiche moderne.

Il generatore PCG di base è un generatore a 32 bit con 64 bit di stato e 63 bit utilizzati per selezionare il flusso: è come avere 9.223.372.036.854.775.808 codici, ciascuno riempito con 18.446.744.073.709.551.616 numeri (interi a 32 bit).
Si tratta di “numeri” che rendono i dati generati davvero vicini alla casualità “reale”: probabilmente è più facile prevedere i tiri dei dadi o indovinare i numeri che usciranno alla roulette.

La caratteristica principale del PCG è che combina l’efficienza computazionale dell’algoritmo LCG con la buona qualità statistica della funzione di permutazione. Quest’ultima, in particolare, permette di rimuovere le correlazioni tra i numeri generati con l’algoritmo LCG migliorando la distribuzione dei numeri pseudocasuali.

Sul Web è disponibile un interessante confronto da generatori di numeri pseudocasuali elaborato sempre da O’Neill che mette in evidenza come il suo PCG superi le varie alternative in termini di qualità statistica, difficoltà di previsione, risultati riproducibili, flussi multipli, periodo, funzionalità utili, prestazioni, utilizzo dello spazio, dimensione e complessità del codice.