I numeri casuali non sono casuali…

Voglio essere chiaro, questo non è un altro articolo che parla di numeri random.

Ecco cosa non troverete in questo articolo, un lungo trattato sui numeri random e sul loro raggruppamento (sequenza casuale), sulle loro proprietà e sul perché essi sono di vitale importanza per l’essere umano moderno. Allora, di cosa si parlerà in questo articolo?

Mi fa piacere ve lo stiate chiedendo; in questo articolo si parlerà di come non sia possibile ottenere sequenze di numeri casuali mediante un computer tradizionale e di quali sono gli artifici che possiamo utilizzare per simulare una sequenza di numeri casuali.

Prima di addentrarci in dettagli complicati, poniamoci la vera domanda fondamentale riguardo i numeri casuali e le sequenze di numeri casuali. Perché sono cosi importanti per noi? Sì lo so, avevo detto che non avrei parlato di questo ma una piccola introduzione è d’obbligo per inquadrare il contesto in cui ci stiamo muovendo.

Ritornando alla nostra domanda (perché i numeri casuali e le loro sequenze sono cosi importanti?), le risposte sono molteplici, qualcuno vi citerà i criteri di crittografia che proteggono le vostre mail, password, pin della carta di credito. Poi c’è chi, invece, realmente ne coglie il significato; i numeri casuali sono importanti perché sono alla base dei videogames. I numeri casuali sono alla base di tutti i videogiochi e questa è una ragione più che sufficiente per studiarne le proprietà.

Bene, partiamo con il primo concetto, quello forse più importante. In un qualsiasi computer moderno, usando un qualsiasi linguaggio di programmazione (c/c++, python, MatLab per citare quelli maggiormente usati per il calcolo scientifico) una sequenza di numeri casuali  viene generata mediante un algoritmo.

Cosa è un algoritmo? Un algoritmo è una insieme di istruzioni o di passi o di azioni da compiere per manipolare un dato in input in modo da ottenere un dato di output. Questa sequenza di passi deve essere ben determinata e non può generare un risultato a caso. La prerogativa più importante di un algoritmo è che, dato lo stesso input viene generato sempre lo stesso output. Quindi, se per generare una sequenza di numeri casuali usiamo un algoritmo e un algoritmo non è casuale (stesso input genera lo stesso output) si evince da se che non è possibile generare numeri casuali mediante un normale computer o linguaggio di programmazione.

Non ci resta che barare!

Quindi, cosa dovremmo fare? Arrenderci e non generare più sequenze di numeri casuali con un computer? Giammai!

Prima di sprofondare nell’anarchia generale fermiamoci un attimo a pensare che, come spesso accade, quello che è impossibile per un matematico o un fisico diventa una buona approssimazione per un ingegnere (meno male che ci sono loro a salvarci).

Oggi sono disponibili diversi algoritmi per la generazione di numeri non casuali ma che si comportano come tali, i così detti numeri pseudo-casuali. Gli algoritmi oggi utilizzati sono di differente complessità e richiedono diversi tempi di esecuzione. Quanto maggiore è la complessità tanto maggiore sarà la casualità dei numeri generati. In realtà, quello che cambia tra i vari metodi, è il numero di valori da dover tirare fuori prima che una ripetizione o schema possa essere trovato all’interno della sequenza. Gli algoritmi oggi utilizzati maggiormente non generano davvero numeri random all’infinito. Generano una sequenza pseudo-casuale con un numero finito di termini, grande ma finito. Questo vuol dire che dopo un certo punto la sequenza comincerà a ripetersi uguale a se stessa.

Due algoritmi per la generazione di numeri pseudo-casuali sono:

  • LCG (linear congruential generator o generatori lineari congruenziali); furono i primi ad essere sviluppati e sono tutt’ora i più utilizzati in quanto presentano un buon compromesso tra velocità e livello di complessità.

 

  • lagged Fibonacci, o generatori di Fibonacci ritardati; più complessi dei precedenti con un periodo di $${2}^{19937} -1$$ prima di ripetersi (algoritmo Twister).

I due algoritmi esposti sono dei generatori di numeri casuali che usano, rullo di tamburi, un equazione per generare la sequenza di numeri casuali. Nel caso di generatori LCG la funzione implementata è

$${X}_{n+1}=(a{X}_{n}+c) (mod$$  $$m)$$

dove a, c ed m sono numeri scelti per generare la sequenza. L’operazione (mod m) indica il resto della divisione tra il primo termine tra parentesi tonde ed m. Per questa sequeza il periodo massimo prima di una ripetizione è pari al valore di m; in pratica questa condizione si verifica solo per particolari scelte dei parametri a, c ed m e risulta quindi essere sempre minore. Questo algoritmo, tre le tante applicazioni, è utilizzato dalle API random di java, da gcc e da Borland per la propria distribuzione di C/C++ e Pascal.

Il secondo algoritmo, il lagged Fibonacci, ha invece un equazione simile a quella utilizzata per generare una sequenza di Fibonacci, da cui prende il nome:

$${F}_{n}={F}_{n-j}*{F}_{n-k} (mod$$ $$m)$$

in questo caso * indica una qualsiasi operazione binaria. Nel caso l’operatore sia la moltiplicazione l’algoritmo viene detto moltiplicativo o ritardato. Anche in questo caso l’algoritmo ha un periodo che dipende dalle particolari scelte di k ed m. In particolare  per questo tipo di algoritmo l’uso della somma come operazione binaria aumenta il periodo rispetto all’uso della moltiplicazione.

Segreti non segreti

Gli algoritmi ora presentati, per come sono definiti, non possono essere usati per la crittografia in quanto intrinsecamente deboli.

 Per scopi in cui la sicurezza è un fattore determinante occorre usare algoritmi di tipo diverso, più sicuri e più casuali se cosi possiamo dire.

Tra gli algoritmi usati per la crittografia uno dei più comuni è chiamato Fortuna. Tale algoritmo è in realtà una famiglia di PRNG (Pseudo Random Number Generator) in quanto alcuni dei suoi parametri sono modificabili dando origine a diverse configurazioni.

Il nome dell’algoritmo, Fortuna, è un chiaro richiamo alla dea del caso della mitologia greca, almeno secondo i suoi creatori Bruce Schneier e Niels Ferguson.

Come funziona l’algoritmo? Esso è composot da tre parti. Un generatore di numeri che inizializzato con un seme genererà una sequenza di numeri casuali; un accumulatore di entropia che raccoglie dati da vari dispositivi (mouse, tastiera, etc) e li accumula, questi dati vengono poi utilizzati per rinnovare il seed del generatore; un file di seed che slava alcuni dei dati random utilizzati dal generatore in modo da inizializzarlo all’avvio del pc quando l’accumulatore di entropia non è ancora pieno.

L’algoritmo cosi ottenuto è quindi molto più sicuro in quanto basato su una quantità di dati generalmente molto grande e che può considerarsi più o meno casuale (pensiamo ai movimenti del mouse sullo schermo che vengono utilizzati per generare le sequenze).

Cosa possiamo fare?

Abbiamo visto come i numeri casuali, quelli che chiamiamo tali, in realtà non lo sono. Vengono generati tramite un algoritmo che come tale non è casuale per sua stessa definizione. Di conseguenza, i computer generaro sequenze di numeri pseudocasuali, sequenze di numeri definite prevedibili che hanno le proprietà dei numeri casuali se presi non troppi alla volta (al massimo un numero pari al periodo) e vengono utilizzati per le applicazioni quotidiane tra cui anche i videogiochi.

Esistono alcuni algoritmi che cercano di rendere le cose più complicate, acquisiscono dati random dalle periferiche (mouse, tastiera, etc) e li usano per generare delle sequenze più casuali e possono quindi essere usati per la crittografia e la sicurezza informatica.

Ora che sapete la verità sta a voi scegliere. Potete ignorare quanto scritto in questo articolo, tornare alla vostra vita e continuare a credere che i numeri casuali sono davvero casuali; oppure, potete prendere coscienza di quanto avete appena letto e la prossima volta che vi accingerete ad usare la funzione random, qualunque codice sia, sapere che i numeri generati sono prevedibili, definiti e ripetibili con tutto ciò che questo comporta.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.