Pseudo-slučajni broj je poseban broj generiran posebnim generatorom. Deterministički nasumični generator bitova (PRNG), poznat i kao deterministički nasumični generator bitova (DRBG), je algoritam za generisanje niza brojeva čija svojstva su približna karakteristikama nizova slučajnih brojeva. Generirana PRNG sekvenca nije zaista nasumična, jer je u potpunosti određena početnom vrijednošću koja se zove PRNG sjeme, koja može uključivati istinski slučajne vrijednosti. Iako se sekvence koje su bliže nasumičnom mogu generirati pomoću hardverskih generatora slučajnih brojeva, generatori pseudoslučajnih brojeva su važni u praksi zbog brzine generiranja brojeva i njihove reproducibilnosti.
Prijava
PRNG-ovi su centralni za aplikacije kao što su simulacija (npr. za Monte Carlo), elektronske igre (npr. za proceduralno generisanje) i kriptografija. Kriptografske aplikacije zahtijevaju taj izlazpodaci nisu bili predvidljivi iz ranijih informacija. Potrebni su složeniji algoritmi koji ne nasljeđuju linearnost jednostavnih PRNG-ova.
Uslovi i odredbe
Dobra statistička svojstva su centralni uslov za dobijanje PRNG-a. Općenito, potrebna je pažljiva matematička analiza kako bi se osiguralo da RNG generiše brojeve koji su dovoljno bliski nasumičnom da bi bili prikladni za namjeravanu upotrebu.
John von Neumann je upozorio na pogrešno tumačenje PRNG-a kao istinski slučajnog generatora i našalio se da je "Svako ko razmatra aritmetičke metode za generiranje slučajnih brojeva sigurno u stanju grijeha."
Koristite
PRNG se može pokrenuti iz proizvoljnog početnog stanja. Uvijek će generirati isti niz kada se inicijalizira ovim stanjem. PRNG period je definiran na sljedeći način: maksimum u svim početnim stanjima dužine prefiksa sekvence koja se ne ponavlja. Period je ograničen brojem stanja, obično se mjeri u bitovima. Budući da se dužina perioda potencijalno udvostručuje sa svakim dodanim bitom "stanja", lako je kreirati PRNG-ove s periodima dovoljno velikim za mnoge praktične primjene.
Ako unutrašnje stanje PRNG-a sadrži n bitova, njegov period ne može biti veći od 2n rezultata, mnogo je kraći. Za neke PRNG-ove, trajanje se može izračunati bez zaobilaženja cijelog perioda. Linearni registri pomaka sa povratnom spregom (LFSR) su tipičnobiraju se tako da imaju periode jednake 2n − 1.
Linearni kongruencijalni generatori imaju periode koji se mogu izračunati korištenjem faktoringa. Iako će PPP ponoviti svoje rezultate nakon što dođu do kraja perioda, ponovljeni rezultat ne znači da je kraj perioda dostignut, jer njegovo unutrašnje stanje može biti veće od izlaza; ovo je posebno vidljivo za PRNG-ove sa izlazom jednog bita.
Moguće greške
Greške koje pronađu neispravni PRNG-ovi kreću se od suptilnih (i nepoznatih) do očiglednih. Primjer je RANDU algoritam slučajnih brojeva, koji se decenijama koristi na glavnim računarima. Bio je to ozbiljan nedostatak, ali je njegova neadekvatnost dugo vremena ostala neprimijećena.
U mnogim oblastima, istraživačke studije koje su koristile slučajni odabir, Monte Carlo simulacije ili druge metode zasnovane na RNG-u su mnogo manje pouzdane nego što bi mogle biti rezultat lošeg kvaliteta GNPG-a. Čak i danas, ponekad je potreban oprez, o čemu svjedoči upozorenje u Međunarodnoj enciklopediji statističkih nauka (2010).
Uspješna studija slučaja
Kao ilustraciju, razmotrite široko korišćeni programski jezik Java. Od 2017. Java se i dalje oslanja na linearni kongruencijalni generator (LCG) za svoj PRNG.
Historija
Prvi PRNG koji izbjegava ozbiljne probleme i još uvijek radi prilično brzo,bio je Mersenne Twister (o kome se govori u nastavku), koji je objavljen 1998. Od tada su razvijeni drugi visokokvalitetni PRNG-ovi.
Ali istorija pseudoslučajnih brojeva se tu ne završava. U drugoj polovini 20. veka, standardna klasa algoritama korišćenih za PRNG-ove uključivala je linearne kongruencijalne generatore. Poznato je da je kvalitet LCG-a neadekvatan, ali bolje metode nisu bile dostupne. Press et al (2007) opisali su rezultat na sljedeći način: "Kada bi svi naučni radovi čiji su rezultati sumnjivi zbog [LCGs i srodnih] nestali s polica biblioteke, na svakoj polici bi bio jaz veličine vaše šake."
Glavno dostignuće u stvaranju pseudo-slučajnih generatora bilo je uvođenje metoda zasnovanih na linearnom rekurentu u polju sa dva elementa; takvi oscilatori su spojeni na registre pomaka s linearnom povratnom spregom. Oni su poslužili kao osnova za pronalazak senzora pseudo-slučajnih brojeva.
Naročito, izum Mersena Twistera iz 1997. izbjegao je mnoge probleme sa ranijim generatorima. Mersenne Twister ima period od 219937−1 iteracija (≈4,3 × 106001). Dokazano je da je ravnomjerno raspoređen u (do) 623 dimenzije (za 32-bitne vrijednosti), a u vrijeme svog uvođenja bio je brži od drugih statistički zvučnih generatora koji proizvode pseudo-slučajne nizove brojeva.
U 2003. George Marsaglia je predstavio familiju generatora xorshifta također zasnovanih na linearnom ponavljanju. Ovi generatori su izuzetnobrzi su i - u kombinaciji s nelinearnim radom - prolaze rigorozne statističke testove.
U 2006. godini razvijena je porodica generatora WELL. DOBRO generatori na neki način poboljšavaju kvalitetu Twister Mersennea, koji ima preveliki prostor stanja i vrlo spor oporavak od njih, generirajući pseudoslučajne brojeve sa puno nula.
Kriptografija
PRNG pogodan za kriptografske aplikacije naziva se kriptografski siguran PRNG (CSPRNG). Zahtjev za CSPRNG je da napadač koji ne poznaje seme ima samo marginalnu prednost u razlikovanju izlazne sekvence generatora od nasumične sekvence. Drugim riječima, dok je PRNG potreban samo da prođe određene statističke testove, CSPRNG mora proći sve statističke testove koji su ograničeni na polinomsko vrijeme u veličini sjemena.
Iako je dokaz ovog svojstva izvan trenutnog nivoa teorije računske složenosti, jaki dokazi se mogu pružiti svođenjem CSPRNG-a na problem koji se smatra teškim, kao što je faktorizacija cijelih brojeva. Generalno, mogu biti potrebne godine pregleda prije nego što se algoritam može certificirati kao CSPRNG.
Pokazano je da je vjerovatno da je NSA ubacila asimetrična stražnja vrata u NIST-certificirani Dual_EC_DRBG generator pseudo-slučajnih brojeva.
Pseudo-slučajni algoritmibrojevi
Većina PRNG algoritama proizvodi sekvence koje su ravnomjerno raspoređene bilo kojim od nekoliko testova. Ovo je otvoreno pitanje. To je jedno od središnjih u teoriji i praksi kriptografije: postoji li način da se razlikuje izlaz visokokvalitetnog PRNG-a od istinski slučajnog niza? U ovoj postavci, razrješavač zna da je korišten ili poznati PRNG algoritam (ali ne i stanje s kojim je inicijaliziran), ili je korišten istinski slučajni algoritam. Mora razlikovati između njih.
Sigurnost većine kriptografskih algoritama i protokola koji koriste PRNG-ove zasniva se na pretpostavci da je nemoguće napraviti razliku između upotrebe odgovarajućeg PRNG-a i upotrebe zaista slučajnog niza. Najjednostavniji primjeri ove zavisnosti su stream šifre, koje najčešće rade tako što izostavljaju ili šalju poruku otvorenog teksta sa PRNG izlazom, proizvodeći šifrirani tekst. Dizajniranje kriptografski adekvatnih PRNG-ova je izuzetno teško jer moraju ispuniti dodatne kriterije. Veličina njegovog perioda je važan faktor u kriptografskoj podobnosti PRNG-a, ali ne i jedini.
Rani kompjuterski PRNG koji je predložio John von Neumann 1946. poznat je kao metoda srednjih kvadrata. Algoritam je sljedeći: uzmite bilo koji broj, kvadrirajte ga, uklonite srednje cifre rezultirajućeg broja kao "slučajni broj", a zatim koristite ovaj broj kao početni broj za sljedeću iteraciju. Na primjer, kvadriranje broja 1111 daje1234321, koji se može zapisati kao 01234321, osmocifreni broj je kvadrat 4-cifrenog broja. Ovo daje 2343 kao "slučajni" broj. Rezultat ponavljanja ove procedure je 4896, i tako dalje. Von Neumann je koristio 10-cifrene brojeve, ali je proces bio isti.
Nedostaci "srednjeg kvadrata"
Problem sa metodom "srednjeg kvadrata" je taj što se sve sekvence na kraju ponavljaju, neke vrlo brzo, na primjer: 0000. Von Neumann je znao za ovo, ali je pronašao pristup koji je dovoljan za njegove svrhe i brinuo se da će matematičke "ispravke" bi samo sakrile greške umjesto da ih uklone.
Von Neumann je utvrdio da su hardverski generatori slučajnih i pseudo-slučajnih brojeva neprikladni: ako ne zabilježe generirani izlaz, kasnije se ne mogu provjeriti ima li grešaka. Ako bi zapisali svoje rezultate, iscrpili bi ograničenu raspoloživu memoriju računara, a time i sposobnost računara da čita i piše brojeve. Kada bi brojevi bili napisani na karticama, trebalo bi im mnogo duže za pisanje i čitanje. Na računaru ENIAC koji je koristio metodu "srednjeg kvadrata" i izvršio proces dobijanja pseudoslučajnih brojeva nekoliko stotina puta brže od čitanja brojeva sa bušenih kartica.
Srednji kvadrat je od tada zamijenjen složenijim generatorima.
Inovativna metoda
Nedavna inovacija je kombinovanje srednjeg kvadrata sa Weilovim nizom. Ova metoda osigurava visoku kvalitetu proizvoda iznutradug period. Pomaže da dobijete najbolje formule pseudo-slučajnih brojeva.
