Pseudo-slučajni broj je poseban broj generiran posebnim generatorom. Deterministički Random Bit Generator (PRNG), također poznat kao Deterministički Random Bit Generator (DRBG), je algoritam za generiranje niza brojeva čija svojstva su približna karakteristikama nizova slučajnih brojeva. Generirani PRNG slijed nije uistinu nasumičan, jer je u potpunosti određen početnom vrijednošću koja se naziva PRNG sjeme, a koja može uključivati uistinu 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 važni su u praksi za brzinu generiranja brojeva i njihovu reproducibilnost.
Prijava
PRNG-ovi su središnji za aplikacije kao što su simulacija (npr. za Monte Carlo), elektroničke igre (npr. za proceduralno generiranje) i kriptografija. Kriptografske aplikacije zahtijevaju da izlazpodaci nisu bili predvidljivi iz ranijih informacija. Potrebni su složeniji algoritmi koji ne nasljeđuju linearnost jednostavnih PRNG-ova.
Uvjeti i odredbe
Dobra statistička svojstva središnji su uvjet za dobivanje PRNG-a. Općenito, potrebna je pažljiva matematička analiza kako bi se osiguralo da RNG generira brojeve koji su dovoljno bliski nasumičnom da budu prikladni za namjeravanu upotrebu.
John von Neumann upozorio je na pogrešno tumačenje PRNG-a kao istinski slučajnog generatora i našalio se da "Svatko tko razmatra aritmetičke metode za generiranje slučajnih brojeva sigurno je u stanju grijeha."
Koristite
PRNG se može pokrenuti iz proizvoljnog početnog stanja. Uvijek će generirati isti slijed kada se inicijalizira s ovim stanjem. Razdoblje PRNG definirano je kako slijedi: maksimalno preko svih početnih stanja duljine prefiksa sekvence koja se ne ponavlja. Razdoblje je ograničeno brojem stanja, obično se mjeri u bitovima. Budući da se duljina razdoblja potencijalno udvostručuje sa svakim dodanim bitom "stanja", lako je stvoriti PRNG-ove s periodima dovoljno velikim za mnoge praktične primjene.
Ako unutarnje 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 razdoblja. Linearni registri pomaka s povratnom spregom (LFSR) su tipičnibiraju se tako da imaju periode jednake 2n − 1.
Linearni kongruencijalni generatori imaju periode koji se mogu izračunati korištenjem faktoringa. Iako će JPP ponoviti svoje rezultate nakon što dođu do kraja razdoblja, ponovljeni rezultat ne znači da je dosegnut kraj razdoblja, budući da njegovo unutarnje stanje može biti veće od outputa; ovo je posebno vidljivo za PRNG-ove s jednobitnim izlazom.
Moguće pogreške
Pogreške koje pronađu neispravni PRNG-ovi kreću se od suptilnih (i nepoznatih) do očitih. Primjer je RANDU algoritam slučajnih brojeva, koji se desetljećima koristi na glavnim računalima. Bio je to ozbiljan nedostatak, ali njegova je neadekvatnost dugo vremena ostala nezapažena.
U mnogim područjima, istraživačke studije koje su koristile slučajni odabir, Monte Carlo simulacije ili druge metode temeljene na RNG-u su mnogo manje pouzdane nego što bi mogle biti rezultat loše kvalitete GNPG-a. Čak i danas ponekad je potreban oprez, o čemu svjedoči upozorenje u Međunarodnoj enciklopediji statističkih znanosti (2010).
Uspješna studija slučaja
Kao ilustraciju, razmotrite široko korišteni programski jezik Java. Od 2017. Java se i dalje oslanja na linearni kongruentni generator (LCG) za svoj PRNG.
Povijest
Prvi PRNG koji izbjegava ozbiljne probleme i još uvijek radi prilično brzo,bio je Mersenne Twister (o kojem se govori u nastavku), koji je objavljen 1998. godine. Od tada su razvijeni drugi visokokvalitetni PRNG-ovi.
Ali povijest pseudoslučajnih brojeva tu ne završava. U drugoj polovici 20. stoljeća, standardna klasa algoritama korištenih za PRNG-ove uključivala je linearne kongruencijalne generatore. Poznato je da je kvaliteta LCG-a neadekvatna, ali bolje metode nisu bile dostupne. Press i suradnici (2007) opisali su rezultat na sljedeći način: "Kada bi svi znanstveni radovi čiji su rezultati upitni zbog [LCG-a i srodnih] nestali s polica knjižnice, na svakoj bi polici postojao jaz veličine vaše šake."
Glavno postignuće u stvaranju pseudo-slučajnih generatora bilo je uvođenje metoda baziranih na linearnom rekurentu u polju s dva elementa; takvi su oscilatori spojeni na registre pomaka s linearnom povratnom spregom. Oni su poslužili kao osnova za izum senzora pseudoslučajnih brojeva.
Konkretno, izum Mersena Twistera iz 1997. izbjegao je mnoge probleme s ranijim generatorima. Mersenne Twister ima razdoblje od 219937−1 iteracija (≈4,3 × 106001). Dokazano je da je jednoliko raspoređen u (do) 623 dimenzije (za 32-bitne vrijednosti), a u vrijeme svog uvođenja bio je brži od ostalih statistički zvučnih generatora koji proizvode pseudo-slučajne nizove brojeva.
U 2003., George Marsaglia je predstavio obitelj xorshift generatora također temeljenih na linearnom ponavljanju. Ovi generatori su izuzetnobrzi su i - u kombinaciji s nelinearnim radom - prolaze rigorozne statističke testove.
U 2006. godini razvijena je obitelj 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 s puno nula.
Kriptografija
PRNG prikladan za kriptografske aplikacije naziva se kriptografski siguran PRNG (CSPRNG). Zahtjev za CSPRNG je da napadač koji ne poznaje sjeme ima samo marginalnu prednost u razlikovanju izlazne sekvence generatora od slučajnog niza. 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 trenutne razine teorije računske složenosti, jaki dokazi mogu se pružiti redukcijom CSPRNG-a na problem koji se smatra teškim, poput cjelobrojne faktorizacije. Općenito, mogu biti potrebne godine pregleda prije nego što se algoritam može certificirati kao CSPRNG.
Pokazano je da je vjerojatno da je NSA umetnula asimetrična stražnja vrata u generator pseudoslučajnih brojeva Dual_EC_DRBG s certifikatom NIST.
Pseudo-slučajni algoritmibrojevi
Većina PRNG algoritama proizvodi sekvence koje su ravnomjerno raspoređene bilo kojim od nekoliko testova. Ovo je otvoreno pitanje. Ono je jedno od središnjih u teoriji i praksi kriptografije: postoji li način da se razlikuje izlaz visokokvalitetnog PRNG-a od uistinu 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 ih razlikovati.
Sigurnost većine kriptografskih algoritama i protokola koji koriste PRNG-ove temelji se na pretpostavci da je nemoguće razlikovati korištenje prikladnog PRNG-a i korištenje uistinu slučajnog niza. Najjednostavniji primjeri ove ovisnosti su šifre toka, koje najčešće rade tako što izostavljaju ili šalju poruku otvorenog teksta s PRNG izlazom, stvarajući šifrirani tekst. Dizajniranje kriptografski primjerenih PRNG-ova iznimno je teško jer moraju zadovoljiti dodatne kriterije. Veličina njegovog razdoblja važan je čimbenik u kriptografskoj prikladnosti PRNG-a, ali ne i jedini.
Rani računalni 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 znamenke rezultirajućeg broja kao "slučajni broj", a zatim ovaj broj koristite kao početni broj za sljedeću iteraciju. Na primjer, kvadriranje broja 1111 daje1234321, koji se može napisati kao 01234321, 8-znamenkasti broj je kvadrat četveroznamenkastog broja. Ovo daje 2343 kao "slučajni" broj. Rezultat ponavljanja ovog postupka je 4896 i tako dalje. Von Neumann je koristio 10-znamenkaste brojeve, ali je proces bio isti.
Nedostaci "srednjeg kvadrata"
Problem s metodom "srednjeg kvadrata" je taj što se sve sekvence na kraju ponavljaju, neke vrlo brzo, na primjer: 0000. Von Neumann je znao za to, ali je pronašao pristup koji je dovoljan za njegove svrhe i brinuo se da će matematičke "ispravke" samo bi sakrile pogreške umjesto da ih uklone.
Von Neumann smatra 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čunala, a time i sposobnost računala da čita i piše brojeve. Kad bi brojevi bili napisani na karticama, trebalo bi im puno duže za pisanje i čitanje. Na računalu ENIAC koristio je metodu "srednji kvadrat" i proveo proces dobivanja pseudoslučajnih brojeva nekoliko stotina puta brže od čitanja brojeva s bušenih kartica.
Srednji kvadrat je od tada zamijenjen složenijim generatorima.
Inovativna metoda
Nedavna inovacija je kombiniranje srednjeg kvadrata s Weilovim nizom. Ova metoda osigurava unutarnju visoku kvalitetu proizvodadugo razdoblje. Pomaže dobiti najbolje formule pseudoslučajnih brojeva.
