L’eterna sfida dei numeri casuali

Non lo sai? Spara a caso! Niente di più facile per un [del]complottista[/del] uomo, ma per una macchina la situazione cambia notevolmente.

La generazione dei numeri casuali è troppo importante per essere lasciata al caso.

La generazione di numeri random da parte di un computer è una cosa che mi ha sempre affascinato, fin da quando giocavo a Fifa International Soccer sul mio glorioso Pentium 75.

La casualità è un concetto che, ad un processore, proprio non entra in testa!

È come parlare di metodo scientifico ad un sostenitore dell’omeopatia.

I numeri casuali

Innanzitutto vediamo esattamente cosa sia un numero casuale. Il matematichese non mi piace quindi vediamo di spiegarlo in altri modi.

Perchè una sequenza di numeri sia considerata casuale devono essere soddisfatte 2 caratteristiche:

• avere una distribuzione ben definita.
• non essere prevedibili.

Considerando l’esempio più usato, quello del lancio di un dado ripetuto n volte, le nostre due condizioni devono essere verificate in questo modo:

• Prendendo  l’intervallo [1,6] ed al crescere dei lanci, ogni singolo numero che  compone questo intervallo deve avere la stessa frequenza di “uscita”, ovvero ⅙ (nel nostro caso).
• Non solo però : conoscendo il numero ottenuto dal primo lancio non devo essere in grado di prevedere il risultato di quello successivo.

Tutto questo applicato ai dadi sembra molto banale ma in realtà non lo è.

Perché, per esempio, potremmo volere una distribuzione diversa e non uniforme, tale quindi da assegnare “pesi” diversi ai vari valori.

Oppure mettiamo in piedi un sito di poker on-line e vogliamo sapere a priori che carta uscirà dopo il 3 di cuori (stiamo ovviamente facendo solo degli esempi, quei gentiluomini del gioco d’azzardo mica sono così diabolici!).

Datemi un input e vi solleverò il mondo

Ma noi siamo informatici, non matematici. Non ci complichiamo la vita in inutili piagnistei. Quello che vorrei far notare quindi è che, quando vi fanno scegliere un numero a caso, non vi danno alcun input.
Un conto infatti è dirvi:

• Quanto fa 4 per 3?
• Quale è la prima città che ti viene in mente con la lettera R?

Un altro è:

• Dimmi un numero ( o città ) a caso!

Questo in informatica generalmente è un male. Il computer è un drago a processare degli input ma senza un valore di ingresso non va da nessuna parte. E siamo così al primo vero grosso problema nella generazione di un numero casuale.

Ma non l’unico.

Supponiamo infatti di trovare un maledettissimo input (il come lo vedremo dopo): ora dobbiamo creare un algoritmo che , data una funzione di distribuzione, restituisca dei valori non prevedibili tali però da rispettare le condizioni imposte dalla  distribuzione.

Non solo, sarebbe utile infatti che ci restituisca un numero random compreso in un intervallo ben preciso, perchè non possiamo giocare a scala 40 con i soli 6 valori dei dadi, no?!
Come si dice in questi casi: che sbatta!

Generazione di un numero casuale.

Fortunatamente arrivano in nostro soccorso statistici e matematici che in una bella serata primaverile, non sapendo di che parlare, mentre sorseggiano dell’ acqua e menta disquisiscono del suddetto problema.
Io la scena, ambientata nel 1830, la immagino nel seguente modo.

 Poniamo esistente una diavoleria moderna in grado di fare calcoli alla velocità di un baleno; tale marchingegno a vapore, prenderà il nome di calcolatore.

Volendo sfidare a singolar tenzone la suddetta macchina ai dadi, esiste una funzione matematica che permetta alla diavoleria di ottenere una sequenza verosimile?

Alla domanda risponderà Von Neumann, ma solo 117 anni dopo. Nel 1947 l’eroe di tutti noi informatici elabora un primo algoritmo per generare numeri casuali.

Non era perfetto e non funzionava benissimo ma per diverso tempo è stato il massimo che siamo riusciti a fare.

Il funzionamento era semplice: dato un numero composto da n cifre (che prende il nome di seed, seme) se ne calcola il quadrato.

A questo numero vengono tolte le prime e le ultime  “n/2” cifre. Tale numero viene di nuovo dato in pasto all’algoritmo.

Tutto questo è molto bello, principalmente per 2 motivi:

• ha tempi di esecuzione molto bassi
• è ricorsivo

La prima è una condizione necessaria nella creazione di un algoritmo con il nostro scopo:

non possiamo stare in attesa 5 minuti ogni volta che richiediamo una sequenza random.

Il fatto della ricorsività invece non è fondamentale ma non c’è informatico al mondo che non abbia una venerazione per le funzioni ricorsive.
Ma purtroppo ai matematici non frega nulla nè dell’uno nè dell’altro. Così dicono che il metodo fa schifo per questi altri due motivi:

• per valori di seed uguali abbiamo sequenze identiche
• se durante un’iterazione avrò le n cifre centrali uguali a zero, usando un termine matematico “sono fottuto”

Maledetti matematici, devono sempre lamentarsi.

Se c’è una cosa che odio di più di un matematico che si lamenta è uno che lo fa con ragione. Il metodo di Von Neumann infatti non è un granchè (dio mi perdoni per questa bestemmia).

Da qui in poi così il discorso si complica e nascono diverse tipologie di algoritmi ciascuna con pregi e difetti.

Quella su cui vorrei focalizzare l’articolo è quella degli algoritmi a congruenza lineare, LCG per gli amici.

Un po’ perchè mi stanno simpatici e un po’ perchè hanno come unico punto di fallimento l’applicazione nelle simulazioni di gioco d’azzardo, delle quali poco mi frega. Inoltre sono tra i più utilizzati.

La congruenza lineare

Gli algoritmi di questo tipo permettono di generare una sequenza di numeri casuali partendo, come quello visto precedentemente, da un seme. La formula usata è piuttosto semplice anche se a prima vista può spaventare:

xi+1 = (a * x i + c) (MOD m)

xi è il nostro seme

a e c sono dei coefficienti interni che, una volta ottimizzati, ci permettono di ottenere la sequenza desiderata.

m è la classe di resto che vogliamo applicare. Semplificando è il fattore che ci permette di modificare il range dei valori in uscita (quindi un numero da 1 a 6, per esempio).

Non sto a spiegarvi il tutto, trovate maggiori informazioni nel documento dell’ Università di Roma nelle fonti con anche alcuni esempi al variare dei coefficienti a e c.

Vi basti sapere che l’output di questa funzione ci permette di avere delle sequenze di numeri casuali evitando il problema principale della funzione del caro vecchio Von Neumann, ovvero la comparsa dei temibili “zeri”.

Algoritmi simili a questo, vista la loro bontà,  sono utilizzati anche da SSL, il protocollo di sicurezza che tutti noi utilizziamo ogni giorno per le più svariate applicazioni web (dai servizi Google al pagamento online, giusto per citarne due) e che la NSA usa per sapere il nostro numero di scarpe :troll: .

Infatti come potete vedere da grafico poco sopra (preso dalla pagina wiki di LCG) il metodo non è per nulla male!

Questione di seme

Tutto molto bello ma questo dannato seme dove lo trovo? Già perchè finora abbiamo trovato delle soluzioni più o meno valide ma che richiedono tutte  un presupposto: ricevere in input un numero casuale.
In realtà non è proprio così. O meglio, era così nel caso di Von Neumann.
Ma grazie alla congruenza lineare noi possiamo, ricevuto in input un numero di 15 cifre, avere un numero casuale compreso tra 0 e 6.

Il calcolatore a vapore ringrazia.

In definitiva riusciamo a dire al computer di fornirci non solo un numero “casuale” ma addirittura compreso in un determinato intervallo.
Ma il requisito rimane: avere un numero casuale come input della funzione.
Di solito questo seme viene ottenuto tramite una serie di fattori che dipendono anche dal linguaggio utilizzato. Alcuni esempi possono essere:

• la data corrente o una variante di essa(data attuale, millisecondi, giorno della settimana, ecc)
• parametri interni al sistema (identificativo del processo in uso, numero di processi, occupazione disco, ecc…)
• l’indirizzo ip di provenienza di una chiamata
• la combinazione dei precedenti

[spoiler]

Un paio di esempi concreti: Php usa la funzione random per la gestione delle sessioni.

Non vi sto a raccontare come funzionino perchè la cosa annoierebbe chiunque. Riassumendo al server serve creare un numero identificativo univoco che lo metta in comunicazione con il client.

Tale numero è casuale, creato tramite la congruenza lineare del valore

md5 (client IP . timestamp . microseconds1 . php_combined_lcg()) 

ovvero tutti dati conosciuti. In definitiva il seme è una concatenazione di molti valori che lo rendono univoco in base alle variabili del millisecondo e del richiedente. Concettualmente è la miglior soluzione possibile.

Il protocollo SSL citato in precedenza alcuni anni fa e ben prima di HeartBleed è stato violato.

Questo è successo per un errore su alcuni certificati che venivano generati utilizzando un seme basato esclusivamente sull’ id del processo in uso (PID, nel mondo Linux), invece che su una combinazione di più fattori.

Essendo questo un numero compreso tra 1 e 32768 è bastato poco tempo per “falsificare” alcuni certificati.

[/spoiler]

Una volta che abbiamo questo seed il gioco è fatto: usiamo la congruenza lineare con il modulo che ci pare in modo tale da avere la sequenza desiderata con le giuste caratteristiche di lunghezza e range.

Voglio di più

Tutto quanto visto precedentemente è molto bello ma ha un brutto difetto:

non produce realmente dei numeri casuali!

Questo è dato dal fatto che tutti gli algoritmi di creazione sono di tipo deterministico. Ciò vuol dire che, partendo dallo stesso valore, danno come risultato una identica sequenza di numeri.
Esattamente il problema che aveva il metodo originario di Von Neumann.
Così i matematici, arrabbiati per avere finito lo sciroppo alla menta, si scagliano a bomba:

Casuali un par de ciufoli!

Queste sequenze potete al più chiamarle

Numeri pseudo casuali

Provate voi a dargli torto…

Con lo sviluppo della tecnologia si è arrivati alla creazione di generatori hardware che ovviano a questo enorme problema. In genere sono basati su processi fisici come il rumore (sia esso acustico o fotografico) in modo da fornire dei valori realmente aleatori.
Sono tuttavia ancora poco diffusi e l’informatica mainstream (leggasi il pc col quale la gente si laurea in Youtubologia) è ancora basata sulla cara vecchia pseudocasualità.

Conclusioni

Ad oggi i numeri casuali in informatica non esistono. Ma grazie a degli eroici nerd ( e litri di acqua e menta) siamo riusciti a ottenere qualcosa di molto simile.

In definitiva i metodi oggi utilizzati permettono svariate applicazioni nel campo dell’informatica (simulazioni varie, crittografia, gestione di processi concorrenti) senza generare grossi problemi.

Grazie agli algoritmi in questione possiamo, per esempio, leggere la pagina leganerd.com/random quando non abbiamo voglia di lavorare.

Nei prossimi anni probabilmente assisteremo alla comparsa di numeri realmente casuali grazie allo sviluppo della tecnologia ( se ne parlava anche in questo articolo tempo fa, ora potete capirlo meglio).

In definitiva la generazione di sequenze di numeri realmente casuali è stata e resta una delle più grosse sfide del mondo informatico.

Sfida che verrà vinta solo quando riusciremo a generare un seme casuale.

Note e fonti

Tutto quello che vi ho raccontato è una forte semplificazione sia della storia che dei concetti che stanno dietro alla generazione di numeri casuali. Ma l’importante era farvi capire il concetto che sta alla base di tutto questo. Non essendo, come detto, un amante del matematichese potrei avere scritto delle inesattezze: come sempre segnalatemele!

• Qui la pagina wiki dei numeri pseudo casuali
• Qui e qua problemi riguardanti la sicurezza sulla prevedibilità dei numeri pseudo casuali (attenzione, è roba da informatici: ho visto gente morire)
• Un pdf dell’ Università di Roma che spiega nel dettaglio gli algoritmi LCG.