Numeri pseudo-casuali

Da Wikipedia, l'enciclopedia libera.

Sono detti numeri pseudo-casuali (in inglese pseudo-random numbers) i numeri generati da un algoritmo deterministico che produce una sequenza con le stesse proprietà statistiche di una sequenza di numeri generata da un processo casuale. Tale algoritmo è detto generatore di numeri pseudo-casuali (PRNG, dall'inglese pseudo-random numbers generator).

Le sequenze di numeri pseudo-casuali vengono solitamente generate da un computer e utilizzate per algoritmi basati su processi casuali, come i metodi di tipo Monte Carlo o le applicazioni di crittografia. Quando invece occorrono sequenze di numeri realmente casuali, si utilizza un generatore hardware di numeri casuali.

[modifica] Proprietà

Una sequenza di numeri pseudo-casuali deve soddisfare, al minimo, le seguenti proprietà statistiche:

• distribuzione degli elementi della sequenza secondo una funzione di distribuzione predefinita f(x): di solito si richiede una distribuzione uniforme su un intervallo specificato (equidistribuzione), cioè f(x) = 1/(x_min-x_max) nell'intervallo [x_min,x_max] e f(x) = 0 fuori da tale intervallo.
• indipendenza tra elementi successivi della sequenza: se la funzione di distribuzione per un singolo elemento è f(x), la funzione di distribuzione per le coppie di elementi successivi deve essere F(x,y) = f(x) · f(y).

Ad esempio, la sequenza 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 non si può definire pseudo-casuale, in quanto soddisfa il requisito dell'equidistribuzione (sull'intervallo [1,10]), ma non quello dell'indipendenza: le coppie di elementi successivi non sono uniformemente distribuite sull'insieme di tutte le possibili coppie di numeri da 1 a 10, ma sono tutte della forma (n,n+1) (quindi disegnandole su un grafico cartesiano si dispongono tutte sulla stessa retta). Una sequenza pseudo-casuale potrebbe invece essere ad esempio 3, 2, 10, 9, 6, 8, 1, 5, 4, 7: in questo caso le coppie di elementi successivi appaiono distribuirsi in modo abbastanza uniforme sull'insieme delle coppie di numeri da 1 a 10, anche se la lunghezza della sequenza è troppo breve per poterlo verificare accuratamente.

Alcune applicazioni necessitano di altre proprietà statistiche in aggiunta a queste. In particolare, per le applicazioni di crittografia è essenziale che l'algoritmo non permetta di ricostruire l'intera sequenza avendone osservata una parte: altrimenti un malintenzionato potrebbe riprodurre la chiave crittografica generata a partire dalla sequenza e decifrare le informazioni protette da essa. I generatori che soddisfano questo requisito sono detti crittograficamente sicuri (CSPRNG, cryptographically secure PRNG).

[modifica] Algoritmi di generazione

Esistono diverse classi di generatori di numeri pseudo-casuali, che si differenziano per il tipo di algoritmo usato. Nella quasi totalità essi producono una sequenza di numeri interi uniformemente distribuiti tra 0 e un certo valore massimo, oppure di numeri reali tra 0 e 1 (questi ultimi si possono sempre ottenere dai primi semplicemente dividendo per il valore massimo).

Prima di essere usato, un generatore deve essere inizializzato assegnando un opportuno valore a un parametro numerico, o gruppo di parametri, che viene chiamato seme (in inglese seed). Ogni volta che si usa lo stesso seme, si otterrà sempre la stessa identica sequenza.

Un'attenta analisi matematica è richiesta per assicurare che i numeri generati abbiano le necessarie proprietà statistiche. Robert R. Coveyou dell'Oak Ridge National Laboratory ha intitolato un articolo: "La generazione dei numeri casuali è troppo importante per essere lasciata al caso."

Le principali classi di generatori di uso corrente:

• generatori lineari congruenziali (LCG, linear congruential generators): questa è la prima classe in ordine di tempo ad essere stata utilizzata, e tuttora la più diffusa.
• generatori di Fibonacci ritardati (lagged Fibonacci): sono in grado di generare sequenze molto lunghe. Tra questi va segnalato l'algoritmo Mersenne Twister, che ha un periodo di 2¹⁹⁹³⁷-1.
• registri di traslazione a retroazione lineare
• registri di traslazione a retroazione generalizzata

I seguenti sono generatori crittograficamente sicuri:

• Fortuna
• Blum Blum Shub

[modifica] Distribuzioni non uniformi

È possibile generare anche sequenze di numeri pseudo-casuali aventi distribuzione non uniforme: se la forma della distribuzione desiderata è data dalla funzione f(x) (di integrale pari a 1) e se {X_n} è una sequenza di numeri uniformemente distribuiti nell'intervallo [0, 1], una sequenza avente la distribuzione desiderata si ottiene calcolando Y_n = F^-1(X_n), dove F è l'integrale della funzione f.

Per la distribuzione normale, che non è integrabile in forma chiusa, si usa la trasformazione di Box-Muller.

[modifica] Numeri pseudo-casuali in C

Lo standard del linguaggio C (ISO C89) prevede due funzioni dedicate alla generazione di numeri pseudo-casuali:

void srand(unsigned seed);

int rand(void);

La prima funzione inizializza il seme della sequenza, la seconda estrae un numero intero equidistribuito tra 0 e RAND_MAX. Il valore di RAND_MAX dipende dall'implementazione; solitamente è 32767 (2¹⁵-1) oppure 2147483647 (2³¹-1). I prototipi di queste funzioni sono nell'header stdlib.h.

Lo standard non prescrive l'uso di un particolare algoritmo; generalmente viene usato il metodo lineare congruenziale.

[modifica] Esempio

La seguente funzione genera una sequenza pseudo-casuale a 16 bit.

uint random;  // global variable which store the random number (16bit)
void randomNext(void) {
  // update random sequence
  // polinomial alghoritm:
  // +> b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15
  // |     |  |     |                                     |
  // ------+--+-----+-------------------------------------+
  // carry = b1^b2^b4^b15
  // Pn+1=(Pn<<1)|carry
  uchar randomtmp;  // Just a bit flat to accumulate the ex-OR operations
  if (random==0) random++;  // Note: the seed should be != 0
  randomtmp=0;
  if ((uchar)random&0x02) randomtmp=1;
  if ((uchar)random&0x04) randomtmp^=1;
  if ((uchar)random&0x10) randomtmp^=1;
  if (random&0x8000) randomtmp^=1;
  random<<=1;
  (uchar)random|=randomtmp;
}

v · d · m Dispositivi crittografici
Pre era digitale	Calcolatore Bomba · Codici navali giapponesi · Colossus · Cryptex (immaginario) · Enigma · Lorenz SZ 40/42 · Rullo di Jefferson · Siemens and Halske T52
Era digitale	COPACOBANA · Crypto phone · Firma elettronica scritta · Modulo SAM