Numere pseudo-aleatorii

Acestea sunt numite numere pseudo-aleatorii (în engleză numerele generate de un numere pseudo-aleatorii) algoritm determinist care produce o secvență cu aproximativ aceleași statistici de proprietăți ale unei secvențe de numere generate de un proces aleator . Acest algoritm este un generator de numere pseudo-aleatorii (PRNG, englez pseudo-random number generator).

Secvențele de numere pseudo-aleatorii sunt de obicei generate de un computer și utilizate pentru algoritmi bazați pe procese aleatorii, cum ar fi metode similare Monte Carlo sau aplicații criptografice . Pe de altă parte, atunci când sunt necesare secvențe de numere cu adevărat aleatorii, se folosește un generator de numere aleatoare hardware .

Proprietate

O secvență de numere pseudo-aleatorii trebuie să îndeplinească, cel puțin, următoarele proprietăți statistice:

distribuția elementelor secvenței în funcție de o funcție de densitate de probabilitate predefinită $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ : de obicei este necesară o distribuție uniformă într-un interval specificat (echidistribuire), adică $f(x)=1/(x_{max}-x_{min})$ ${\ displaystyle f (x) = 1 / (x_ {max} -x_ {min})}$ ${\ displaystyle f (x) = 1 / (x_ {max} -x_ {min})}$ în interval $[x_{min},x_{max}]$ ${\ displaystyle [x_ {min}, x_ {max}]}$ ${\ displaystyle [x_ {min}, x_ {max}]}$ Și $f(x)=0$ ${\ displaystyle f (x) = 0}$ ${\ displaystyle f (x) = 0}$ în afara acestui interval.
independența între elementele succesive ale secvenței: dacă funcția de distribuție pentru un singur element este f (x), funcția de distribuție pentru perechile de elemente succesive trebuie să fie $f(x,y)=f(x)\cdot f(y)$ ${\ displaystyle f (x, y) = f (x) \ cdot f (y)}$ ${\ displaystyle f (x, y) = f (x) \ cdot f (y)}$ .

De exemplu, secvența 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 nu poate fi definită ca pseudo-aleatorie, deoarece îndeplinește cerința unei distribuții egale (pe interval $[1,10]$ ${\ displaystyle [1,10]}$ ${\ displaystyle [1,10]}$ ), dar nu și a independenței: perechile de elemente succesive nu sunt distribuite uniform pe setul tuturor perechilor posibile de numere de la 1 la 10, dar sunt toate de formă $(n,n+1)$ ${\ displaystyle (n, n + 1)}$ ${\ displaystyle (n, n + 1)}$ (prin urmare, desenându-le pe un grafic cartezian, toate sunt dispuse pe aceeași linie ). O secvență pseudo-aleatorie ar putea fi în schimb, de exemplu, 3, 2, 10, 9, 6, 8, 1, 5, 4, 7: în acest caz perechile de elemente succesive par a fi distribuite destul de uniform pe setul de perechi de numere de la 1 la 10, chiar dacă lungimea secvenței este prea scurtă pentru a fi verificată cu exactitate.

Unele aplicații au nevoie de alte proprietăți statistice în plus față de acestea. În special, pentru aplicațiile criptografice este esențial ca algoritmul să nu permită reconstituirea întregii secvențe, după ce a observat o parte a acesteia: altfel un atacator ar putea reproduce cheia criptografică generată din secvență și decripta informațiile protejate de aceasta. Generatoarele care îndeplinesc această cerință sunt denumite sigure criptografic (CSPRNG, PRNG securizat criptografic).

O altă proprietate semnificativă a unui generator de numere aleatorii este perioada sa, care este numărul de elemente după care se repetă secvența. În general, cu cât perioada este mai lungă, cu atât este mai bună calitatea generatorului, deși pentru majoritatea aplicațiilor o perioadă de $2^{32}-1$ ${\ displaystyle 2 ^ {32} -1}$ $2 ^ {32} -1$ (aproximativ 4 miliarde), care este obținut pentru multe generatoare utilizate în mod obișnuit, este mai mult decât adecvat.

Algoritmi de generare

Există mai multe clase de generatori de numere pseudo-aleatorii, care diferă prin tipul de algoritm utilizat. În aproape toate acestea produc o succesiune de numere întregi distribuite uniform între 0 și o anumită valoare maximă, sau de numere reale între 0 și 1 (aceasta din urmă poate fi întotdeauna obținută din prima pur și simplu împărțind la valoarea maximă).

Înainte de a fi utilizat, un generator trebuie inițializat prin atribuirea unei valori adecvate unui parametru numeric sau unui grup de parametri, care se numește seed (seed în engleză). Ori de câte ori folosiți aceeași sămânță, veți obține întotdeauna aceeași secvență. Prin urmare, perioada unui generator nu poate depăși numărul posibilelor valori ale semințelor: de exemplu, un generator a cărui semință este stocată într-o singură variabilă de 32 de biți poate avea o perioadă maximă de $2^{32}$ ${\ displaystyle 2 ^ {32}}$ ${\ displaystyle 2 ^ {32}}$ (de obicei, valoarea zero nu este permisă și, prin urmare, valorile posibile sunt în vigoare $2^{32}-1$ ${\ displaystyle 2 ^ {32} -1}$ $2 ^ {32} -1$ ).

Este necesară o analiză matematică atentă pentru a se asigura că numerele generate au proprietățile statistice necesare. Robert R. Coveyou de la Oak Ridge National Laboratory a scris un articol: „Generarea numerelor aleatorii este prea importantă pentru a fi lăsată la voia întâmplării”.

Principalele clase de generatoare în uz curent:

Generatoare congruențiale liniare (LCG, generatoare congruențiale liniare): aceasta este prima clasă în ordinea timpului care urma să fie folosită și este încă cea mai răspândită.
generatoare Fibonacci întârziate (Fibonacci întârziate): sunt capabile să genereze secvențe foarte lungi. Printre acestea se numără algoritmul Mersenne Twister , care are o perioadă de $2^{19937}-1$ ${\ displaystyle 2 ^ {19937} -1}$ ${\ displaystyle 2 ^ {19937} -1}$ .
registre de traducere de feedback liniar
registre de traducere a feedback-ului generalizat

Următoarele sunt generatoare sigure criptografic:

Distribuții neuniforme

De asemenea, este posibil să se genereze secvențe de numere pseudo-aleatorii cu distribuție neuniformă: dacă forma distribuției dorite este dată de funcția $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ (cu integral egal cu 1) și dacă $\{x_{n}\}$ ${\ displaystyle \ {x_ {n} \}}$ $\ {x_ {n} \}$ este o succesiune de numere distribuite uniform în interval $[0,1]$ ${\ displaystyle [0,1]}$ $[0, 1]$ , o secvență având distribuția dorită este obținută prin calcul $y_{n}=F^{-1}(x_{n})$ ${\ displaystyle y_ {n} = F ^ {- 1} (x_ {n})}$ ${\ displaystyle y_ {n} = F ^ {- 1} (x_ {n})}$ , unde este $F.$ ${\ displaystyle F}$ $F.$ este funcția integrală sau funcția cumulativă relativă la funcție $f$ ${\ displaystyle f}$ $f$ :

F(x)=\int _{-\infty }^{x}f(y)dy

{\ displaystyle F (x) = \ int _ {- \ infty} ^ {x} f (y) dy}

{\ displaystyle F (x) = \ int _ {- \ infty} ^ {x} f (y) dy}

Și $F^{-1}(x)$ ${\ displaystyle F ^ {- 1} (x)}$ ${\ displaystyle F ^ {- 1} (x)}$ este funcția sa inversă.

Această metodă se numește metoda de inversare .

Exemplu

vrem să generăm numere pseudo-aleatorii distribuite în funcție de distribuție $f(x)=e^{-x}$ ${\ displaystyle f (x) = e ^ {- x}}$ ${\ displaystyle f (x) = e ^ {- x}}$ . Atunci vom avea asta:

F(x)=\int _{0}^{x}e^{-y}dy=1-e^{-x}

{\ displaystyle F (x) = \ int _ {0} ^ {x} e ^ {- y} dy = 1-e ^ {- x}}

{\ displaystyle F (x) = \ int _ {0} ^ {x} e ^ {- y} dy = 1-e ^ {- x}}

.

Și

F^{-1}(x)=-\ln(1-x)

{\ displaystyle F ^ {- 1} (x) = - \ ln (1-x)}

{\ displaystyle F ^ {- 1} (x) = - \ ln (1-x)}

.

Să fie acum $r$ ${\ displaystyle r}$ $r$ variabila noastră aleatorie generată uniform între 0 și 1, să zicem $r=F(x)$ ${\ displaystyle r = F (x)}$ ${\ displaystyle r = F (x)}$ , asa de

x=-\ln(1-r)

{\ displaystyle x = - \ ln (1-r)}

{\ displaystyle x = - \ ln (1-r)}

este o variabilă pseudo-aleatorie generată în funcție de distribuție $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ .

Pentru distribuția normală , care nu este integrabilă în formă închisă, se folosește transformarea Box-Muller .

Numere pseudo-aleatorii în C

Standardul de limbaj C ( ISO C89) oferă două funcții dedicate generării de numere pseudo-aleatorii:

void srand (sămânță nesemnată);

int rand (nul);

Prima funcție inițializează sămânța secvenței, a doua extrage un întreg distribuit uniform între 0 și RAND_MAX . Valoarea RAND_MAX depinde de implementare; de obicei este 32767 ( $2^{15}-1$ ${\ displaystyle 2 ^ {15} -1}$ ${\ displaystyle 2 ^ {15} -1}$ ) sau 2147483647 ( $2^{31}-1$ ${\ displaystyle 2 ^ {31} -1}$ ${\ displaystyle 2 ^ {31} -1}$ ). Prototipurile acestor funcții se află în antetul stdlib.h .

Standardul nu prescrie utilizarea unui anumit algoritm; se folosește în general metoda congruențială liniară.

Exemplu

Următoarea funcție generează o secvență pseudo-aleatorie pe 16 biți.

 uint aleatoriu ; // Variabilă globală unde este stocat numărul aleatoriu (16 biți)
void randomNext ( void ) {
// Actualizați secvența aleatorie
// Algoritm polinomial:
// +> 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 ; // acumulez ex-operațiile OR
if ( random == 0 ) random ++ ; // NB: sămânța trebuie să fie! = 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 ;
aleatoriu << = 1 ;
( uchar ) random | = randomtmp ;
}

Bibliografie

RR Coveyou, Generarea de numere aleatorii este prea importantă pentru a fi lăsată la voia întâmplării, Studii în aplicație. Math., 3, 70-111, 1970.
Donald Knuth . The Art of Computer Programming , Volumul 2: Seminumerical Algorithms , Ediția a treia. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Capitolul 3, pp. 1–193.
John von Neumann , „Diverse tehnici utilizate în legătură cu cifre aleatorii”, în AS Householder, GE Forsythe și HH Germond, eds., Metoda Monte Carlo , National Bureau of Standards Applied Mathematics Series, 12 (Washington, DC: SUA Tipografia guvernamentală, 1951): 36-38.
Recomandarea NIST pentru generarea de numere aleatorii utilizând generatoare de biți aleatori deterministe
Luc Devroye Non-Uniform Random Variate Generation , Springer-Verlag, New York, 1986.

Portal de criptografie

Portalul de matematică

Portal de securitate IT

V · D · M Dispozitive criptografice
Pre era digitală	Calculator bombă · Coduri navale japoneze · Colos · Puzzle · Hebern · Lorenz SZ 40/42 · Cozi violet · Discul Jefferson · Siemens și Halske T52 · Typex · SIGABA
Era digital	COPACOBANA · Telefon cripto · Semnătură electronică scrisă · Modul SAM