Generisanje slučajnih brojeva

мини|Kada se baci kockica, dobije se slučajan broj između 1 i 6. Generator slučajnih brojeva () je računarski ili fizički uređaj dizajniran da generiše niz brojeva ili simbola koji se ne mogu razumno predvideti bolje nego što bi slučajnošću.

Razne primene slučajnosti su dovele do razvoja više različitih metoda za generisanje slučajnih brojeva, neke od tih metoda su postojale još od drevnih vremena, uključujući kocke, bacanje novčića, mešanje karata, korišćenje stabljika hajdučke trave za proricanje u „Ji đingu”, i mnoge druge tehnike. Zbog mehaničke prirode ovih tehnika, generisanje velikog broja dovoljno slučajnih brojeva (bitno u statistici) zahteva puno posla i/ili vremena. Tako, rezultati bi ponekad bili sakupljani i distribuirani kao tabele slučajnih brojeva. Danas, nakon dolaska računarskih generatora slučajnih brojeva, veliki broj lutrija kojima upravljaju vlade su počele da koriste generatore slučajnih brojeva umesto tradicionalnijih metoda izvlačenja. Takođe se koriste za određivanje šansi modernih slot mašina.

Više računarskih metoda postoji za generisanje slučajnih brojeva. Mnogi ne uspevaju da dostignu cilj prave slučajnosti, iako ispunjavaju, sa varirajućim uspehom, neke od statističkih testova slučajnosti namenjenih da mere koliko su nepredvidivi njihovi rezultati (to jest, do kog stepena su njihovi šabloni primetni). Ipak, pažljivo dizajnirani kriptografsko osigurani metodi generisanja slučajnih brojeva takođe postoje, kao što su oni koji su zasnovani na algoritmu hajdučke trave, Fortuna (GPNB), i drugi.

Praktične primene i upotrebe Generatori slučajnih brojeva imaju primene u kockanju, statističkom uzimanju primeraka, računarskoj simulaciji, kriptografiji, kompletno stohastičkom dizajnu, i drugim oblastima gde je poželjno stvarati nepredvidiv rezultat. Generalno, u primenama gde je nepredvidljivost glavna, kao što je u bezbednostnim primenama, hardverski generatori slučajnih brojeva su uglavnom poželjniji od pseudo-slučajnih algoritama.

Generatori slučajnih brojeva su vrlo korisni pri razvijanju simulacija Monte Karlo metoda, jer je debagovanje olakšano mogućnošću da se stvaraju isti nizovi slučajnih brojeva počevši od istog slučajnog semena (). Takođe se koriste u kriptografiji - dok god je seme tajna. Pošiljalac i primalac mogu da generišu isti skup brojeva i da ih automatski koriste kao ključeve.

Generisanje pseudo slučajnih brojeva je bitan i čest zadatak u programiranju. Dok kriptografija i određeni numerički algoritmi zahtevaju veoma visok stepen pseudo slučajnosti, mnoge druge operacije zahtevaju samo skromnu količinu nepredvidljivosti. Neki prosti primer bi mogao biti prikazivanje korisniku „Slučajni citat dana”, ili određivanje kojim putem bi se kompjuterski kontrolisan neprijatelj kretao u video igri. Slabiji oblici slučajnosti se koriste u heš algoritmima i u pravljenju amortizovanih pretraga i algoritama za sortiranje.

Neke primene koje na prvi pogled izgledaju da su prikladne za slučajnost u stvari nisu tako proste. Na primer, sistem koji "slučajno" odabira pesme za pozadinsku muziku mora samo da izgleda slučajno, i možda čak ima načine da kontroliše izbor muzike: pravi slučajni sistem ne bi imao ograničenja da se ista stvar pojavi dva ili tri puta zaredom.

"Pravi" naspram pseudo-slučajnih brojeva Postoje dve glavne metode koje se koriste za generisanje slučajnih brojeva. Prva metoda meri neku fizički pojavu za koju se očekuje da će biti slučajna, a zatim se u procesu merenja eliminiše ne-slučajnost. Izvorni primeri uključuju merenje atmosferskog šuma, termičkog šuma, i ostalih eksternih elektromagnetnih i kvantnih pojava. Na primer, kosmičko pozadinsko zračenje ili radioaktivni raspad mereni tokom kratkih perioda predstavljaju izvor prirodne entropije.

Brzina kojom entropija može da bude sakupljena iz prirodnih izvora zavisi od osnovnih fizičkih pojava koje se mere. Prema tome, za izvore prirodnih pojavljivanja „prave” entropije se kaže da su blokirajući – oni su ograničeni dok nije sakupljeno dovoljno zahtevane entropije. Na nekim sistemima sličnim Juniksu, uključujući većinu Linuks distribucija, pseudo datoteka /dev/random neće dopustiti čitanje dok nije sakupljeno dovoljno entropije iz okoline. Zbog ovog blokiranja, velika sjedinjena čitanja iz /dev/random, kao što je popunjavanje hard diska slučajnim bitovima, može često da uspori sistem koji koriste ovaj tip izvora entropije.

Druga metoda koristi računarske algoritme koji mogu da proizvedu duge nizove od navodno slučajnih rezultata, koji su u stvari u potpunosti određeni manjom početnom vrednošću, poznata kao semena vrednost ili ključ. Kao rezultat, ukupni pseudo-slučajni niz se može stvoriti ako je semena vrednost poznata. Ovaj tip generisanja slučajnih brojeva se često naziva pseudo-slučajni generator brojeva. Ovaj tip generatora se ne oslanja na prirodno pojavljivanje entropije, iako može biti periodično ubačeno seme od strane prirodnih izvora. Ovaj tip generatora ne mora da blokira čitanje, pa nisu ograničeni eksternim događajima, što čini velika sjedinjena čitanja mogućim.

Neki sistemi imaju hibridan pristup, pružajući slučajnost sakupljenu iz prirodnih izvora kada je to moguće, i povlače se periodično da ponovo postave seme softverskim kriptografsko sigurnim pseudo-slučajnim generatorima brojeva (KSPNGB). Povlačenje se dešava kada željena brzina čitanja slučajnosti prevazilazi sposobnost prirodnog sakupljanja da bi mogao da zadovolji potražnju. Ovaj pristup zaobilazi ograničeno blokiranje generatora slučajnih brojeva zasnovanih na sporijim i okolinskim metodama.

Dok generator pseudo-slučajnih brojeva baziran samo na determinističkoj logici ne može nikad biti klasifikovan kao „pravi” izvor slučajnih brojeva u najbukvalnijem smislu reči, u praksi su dovoljni čak i za zahtevne sigurnosno-kritične aplikacije. Pažljivo dizajnirani i implementirani pseudo-slučajni generatori brojeva mogu da se koriste za sigurnosno-kritične kriptografske svrhe, kao što je slučaj sa algoritmom hajdučke trave i fortunom. Algoritam hajdučke trave je osnova za /dev/random izvora entropije na FreeBSD, Aiks, OS X, NetBSD i drugima. OpenBSD takođe koristi pseudo-slučajni numerički algoritam zasnovan na ChaCha20 poznat kao arc4random.

Metode generisanja

Fizičke metode Najranije metode za generisanje slučajnih brojeva, kao što su kocke, bacanje novčića i rulet, se i dalje koriste danas, pre svega u igrama i kockanju jer su prespore za većinu primena u statistici i kriptografiji.

Fizički generator slučajnih brojeva može da se bazira na suštinski slučajnom atomskom ili subatomskom fizičkom fenomenu čija nepredvidivost može da se prati do zakona kvantne mehanike. Izvori entropije uključuju radioaktivnost, termalni šum, statički šum, lavinski šum u Zener diodama, derivacija satova, tempiranje pokreta u tvrdom disku čitaj/piši glave, i radio šuma. Ipak, fizički fenomeni i alati koji se koriste da ih mere generalno sadrže asimetrije i sistematske greške koje čine njihov rezultat ne zaista uniformno slučajan. Izvlačivač slučajnosti, kao što je kriptografska heš funkcija, mogu da se koriste da se približi uniformnoj raspodeli bitova iz neuniformnog slučajnog izvora, mada pri nižoj brzini bitova.

Razni maštoviti načini skupljanja ove entropijske informacije su osmišljeni. Jedna tehnika je da se pokrene heš funkcija na jednu sliku od video striminga iz nepredvidivog izvora. Lavarand je koristio ovu tehniku sa slikama na kojima se nalazi više lava lampi. HotBits meri radioaktivni raspad sa Gajger-Miler cevima, dok Random.org koristi promene u amplitudama atmosferskog šuma snimljenog normalnim radiom.

Drugi čest izvor entropije je ponašanje ljudskih korisnika sistema. Iako se ljudi ne smatraju dobrim generatorom slučajnosti kad se to od njih zahteva, oni generišu slučajna ponašanja prilično dobro u kontekstu igranja igara pomešanih strategija.

Neki kompjuterski softveri u vezi sa bezbednošću zahtevaju da korisnik napravi poduži niz pokreta miša ili pritiska tastature da se napravi dovoljna entropija potrebna za generisanje slučajnih ključeva ili da se inicijalizuje pseudo-slučajni generator brojeva.

Računarske metode

Većina računski generisanih slučajnih brojeva koristi pseudo-slučajne generatore brojeva (PSGB) koji su algoritmi sa mogućnošću automatskog generisanja dugačkog niza brojeva sa dobrim slučajnim svojstvima ali se eventualno niz ponavlja (ili količina utrošene memorije raste bez granica). Ovaj tip slučajnih brojeva su dovoljno dobri u mnogim situacijama ali nisu slučajni koliko i bacanje novčića ili kockica. Niz vrednosti generisan ovakvim algoritmima je obično određen fiksiranom vrednošću koja se naziva seme (). Jedan od najrasprostranjenijih PSGB je linearni kongruentalni generator, koji koristi rekurentnost

da bi generisao brojeve, gde su , and veliki brojevi, i je sledeći u seriji pseudo-slučajnih brojeva. Najveći broj brojeva koje ova formula može proizvesti je modulo . Da bi se izbegla neka ne-slučajna svojstva linearnog kongruentalnog generatora, nekoliko takvih generatora brojeva sa malo drukčijim vrednostima koeficijenta umnožitelja , se mogu koristiti paralelno, sa „master” generatorom brojeva koji odabira između mnoštvo drugih generatora.

Metod olovke i papira za generisanje slučajnih brojeva je takozvani metod srednjeg kvadrata kojeg je za upotrebu predložio Džon fon Nojman. Iako je dati metod jednostavan za implementaciju, njegove izlazne vrednosti su niskog kvaliteta i imaju ozbiljne nedostatke, jedan od tih nedostataka je da dati izlazni niz skoro uvek konvergira ka nuli.

Većina programskih jezika sadrži funkcije ili datoteke zaglavlja sa rutinama koja obezbeđuju generatore slučajnih brojeva. Oni su obično dizajnirani da obezbede slučajan bajt, reč ili broj u pokretnom zarezu ravnomerno raspodeljen između 0 i 1.

Kvalitet slučajnosti ovih funkcija datoteka zaglavlja varira od u potpunosti predvidivih izlaznih vrednosti do kriptografski sigurnih vrednosti. Uobičajen generator slučajnih brojeva u mnogim jezicima, uključujući Pajton, Rubi, R, IDL i PHP je zasnovan na algoritmu Mersenne Twister i nije dovoljan za kriptografske namene, kao što je i rečeno u dokumentaciji nabrojanih programskih jezika. Takve funkcije datoteka zaglavlja obično imaju loša statistička svojstva i neke će ponavljati šablone nakon samo nekoliko desetina hiljada pokušaja. Ove funkcije se obično inicijaliziraju koristeći časovnik samog računara kao seme, pošto takav časovnik obično izračunava vreme u milisekundama, što je daleko više od preciznosti čoveka. Date funkcije mogu da obezbede dovoljno slučajnosti za neke zadatke (npr. video igre) ali su neprikladne za zadatke koji zahtevaju slučajnost visokog kvaliteta, kao što je slučaj u kriptografiji, statistici i numeričkoj analizi.

Izvori slučajnih brojeva mnogo višeg kvaliteta su dostupni na većini operativnih sistema; npr. /dev/random na mnogim Juniks baziranim operativnim sistemima kao što su, Linuks, OS X, IRIKS i Solaris, ili CryptGenRandom za Windows. Većina programskih jezika, uključujući gore navedene, obezbeđuju načine za generisanje visoko kvalitetnih slučajnih brojeva.

Generisanje iz raspodele verovatnoće

Postoji nekoliko metoda generisanja slučajnog broja baziranih na raspodeli verovatnoće. Ove metode uključuju transformisanje (uniformnog) slučajnog broja na neki način. Zbog ovoga, date metode rade podjednako dobro i prilikom generisanja pseudo-slučajnih brojeva i „pravih” slučajnih brojeva. Jedna metoda, koja se naziva metoda inverzije, uključuje integrisanje do površine veće ili jednake slučajnom broju (koja bi trebala da bude generisana između 0 i 1 radi pravilne raspodele). Druga metoda, koja se naziva metoda prihvatanja-odbijanja, uključuje odabiranje i vrednosti i testiranja da li je funkcija od veća od vrednosti . Ako jeste, prihvata se vrednost , u suprotnom vrednost se odbija i algoritam se pokreće ponovo.

Ručne metode