Sadržaj:

0. Uvod

Pojam slučajnih brojeva je u očitoj kontradikciji s pojmom računala kao determinističkih naprava, u kojima se ništa nebi smjelo nepredviđeno događati. Stoga je opravdano postaviti pitanje otkud slučajni brojevi iz naprave koja se nikako nebi smjela ponašati prema nekakvim slučajnostima?

U ovom slučaju se ipak ne radi o brojevima koji su istinski slučajni, nego o brojevima koji se na prvi pogled mogu činit slučajnim, ali način njihovog nastanka u većini slučajeva nije slučajan. Postoji mogućnost dobivanja nizova brojeva nastalih kvantizacijom rezultata nekog istinski stohastičkog procesa, ali takva rješenja su zasad prilično rjetka, pa u većini situacija radimo sa brojevima koji se čine slučajnim, ali to zapravo nisu. Tako nastale brojeve je stoga ispravnije zvati "pseudoslučajnim" brojevima.

U svakom trenutku, na velikom broju računala diljem svjeta računaju se velike količine pseudoslučajnih brojeva. Potreba za brojevima koji su naizgled neovisni jedni od drugima, da bi se izbjeglo ponavljanje identičnih događaja u raznim računalima, raste koliko i raste količina računala u upotrebi. Pseudoslučajni brojevi potrebni su za razne igre i ostale zabavne programe, u čemu zahtjevi za slučajnošću nisu veliki, nego je bitna samo nekakva promjena parametara koji se proglase slučajnima.

Puno ozbiljniji način korištenja jesu raznorazne simulacije, sa raznim slučajnim varijablama, koje generator pseudoslučajnih brojeva mora dobro simulirati. Do izražaja dolazi i raspodjela nastalih brojeva u ukupnom intervalu iz kojega bi brojevi trebali biti, odnosno vjerojatnost pojave svakog broja, ali i ovisnost pojave nekog broja o prethodnim brojevima. Nedovoljno dobra izvedba generatora pseudoslučajnih brojeva dovodi najčešće do krivih rezultata, stoga je potrebno dosta ispitivanja pojedinog generatora da bi se utvrdila njegova valjanost.

Vrlo bitan vid korištenja pseudoslučajnih brojeva danas jest u kriptografiji. Ako se želi ostvariti bilo kakva sigurna komunikacija, potreban je slučajno generiran ključ. U ovom slučaju kvaliteta generatora se očituje u nemogućnosti reprodukcije niza slučajnih brojeva, što onemogućuje eventualno olakšano dolaženje do ključa kojim se kriptiraju poruke. Slab generator u ovom slučaju može postati vrlo lako iskoristiva sigurnosna rupa.

Iz svih ovih razloga, na generatore pseudoslučajnih brojeva se nebi smjelo gledati kao na nešto egzotično. Različite primjene zahtjevaju ogromne količine slučajnih brojeva, stoga njihova implementacija mora biti efikasna, brza i ne pretjerano složena, a opet generator mora biti dovoljno sakriven i složen da ga se nebi moglo iskorisiti kao sigurnostnu slabost. Postoji relativno mnogo metoda za stvaranje pseudoslučajnih brojeva, ali odabir neke od metoda mora biti dobro promišljen, i dobro prilagođen onome što se od generatora traži. Naravno, ovisno o ozbiljnosti funkcije generatora, on mora biti manje ili više testiran na razne načine, da se njegove slabosti nebi pokazale tek preko loših rezultata u stvarnoj upotrebi.

1. Pseudoslučajni brojevi

Gledajući svijet oko sebe, mogu se primjetiti razni nizovi događaja koji se na prvi pogled mogu činiti nepovezanima i slučajnima, bilo to iz razloga nedostatka informacija o tim događajima, ili radi naše nemogućnosti da shvatimo njihovu povezanost. Najčešće su slučajni brojevi dobiveni korištenjem računala, odnosno pseudoslučajni brojevi, dobiveni na neki analogan način, pomoću nekog postupka koji mi u mislima ne možemo rekonstruirati, pa ih stoga smatramo slučajnima.

Kao primjer ovakvog načina razmišljanja, navedimo niz brojeva:

24,16,27,4,1,14,19,13,2,23,21,14.

Na prvi pogled bi se oni mogli činiti slučajnima i nepovezanima, a zapravo nisu. Naime, svaki broj označava poziciju slova u hrvatskoj abecedi, a u ovom poretku ovdje zapravi piše "slučajnibroj". I ovakva mala, zapravo trivijalna, pseudoslučajnost može imati svoju primjenu, ali kasnije ćemo vidjeti manjkavosti ovakvog pristupa.

Svi generatori pseudoslučajnih brojeva se baziraju na rekurzivnim aritmetičkim i/ili logičkim formulama. Prilikom izračunavanja sljedećeg elementa niza slučajnih brojeva možemo se koristiti sa samo jednim ili sa više već izračunatih članova niza, a operacije nad njima mogu biti matematičke, ili ako se gledaju bitovni zapisi brojeva, logičke. Svaki takav generator zahtjeva neku početnu vrijednost, te još nekoliko parametara, koji onda služe kao koeficijenti ili kao konstante.

Svaki generator pseudoslučajnih brojeva, nakon što ga se napravi, valja i dobro ispitati. Ispituju se svojstva perioda ponavljanja niza generiranih brojeva, uniformnost raspodjele brojeva unutar intervala, dok za potrebe simulacija valja znati kako su raspodjeljene n-torke dobivene od n uzastopnih brojeva iz nekog generatora, u n dimenzionalnom prostoru. Također, ako se može pronaći postojeći generator za kojeg se pouzdano zna da ispunjava zahtjeve, te je već korišten i testiran, bolje je primjeniti njega nego ići samostalno programirati novi generator, jer je za takav novi generator potrebno puno testiranja da bi se pokazala njegova primjenjivost.

1-1. Primjeri pseudoslučajnosti temeljeni na aritmetici

Već smo spomenuli da se pseudoslučajnost može postići korištenjem aritmetičkih i logičkih formula. Upotrebljavati se mogu i jednostavne formule, izvedive u samo jednoj liniji programskog koda, ili se može sastaviti neki algoritam s puno aritmetičkih operacija i parametara, te po mogućnosti i logičkim operacijama. Doduše, ne treba smatrati da složen algoritam automatski znači i bolja svojstva generiranih nizova brojeva. Takvo što se smije tvrditi tek nakon testova. Prednost složenih algoritama se može eventualno iskoristiti tamo gdje se način generiranja želi što bolje sakriti, i otežati eventualno pogađanje formule kojom su brojevi dobiveni iz neke količine tih brojeva.

Unutar ovog seminara zadržat ću se na tri jednostavna načina generiranja slučajnih brojeva artimetičkim formulama ili mogućnostima logičke manipulacije bitovnim zapisima brojeva.

1-1-1. Linear congruential generator

Linear congruential generator (zbog jednostavnosti, u daljnjem tekstu ću ovaj pojam označavati oznakom LCG, op.a.) bi se moglo prevesti kao linearni "slijedni" generator pseudoslučajnih brojeva. Artimetička formula za dobivanje brojeva na ovaj način izgleda ovako:

X_n+1 = aX_n + c (mod m)

Svaki LCG je definiran sa četiri parametra, a to su:

X₀ - sjeme (seed) odnosno početni element ovako nastalog niza brojeva

a - koeficijent kojim se množi X_n

c - konstanta koja se nadodaje na umnožak aX_n

m - gornja granica brojeva koji nastaju

Ova formula je prilično jednostavna, programski lako izvediva, i olakšano je eventualno ispitivanje i traženje grešaka u programu koji koristi ovakav način generiranja slučajnih brojeva. S druge strane, jednostavnost ovog načina generiranja pseudoslučajnih brojeva nalaže oprez prilikom korištenja.

Jednostavan način dobivanja realnih slučajnih brojeva od cijelih brojeva jest:

R_n = X_n / m ili R_n = X_n / (m-1)

gdje odabir nazivnika m ili (m-1) ovisi o tome želimo li broj 1 unutar skupa mogućih vrijednosti ili ne.

Bitno je i vidjeti što se događa s periodom dobivenih brojeva. Maksimalni period jest m, ali različitim kombinacijama ostalih parametara može se postići manji period. Za broj m se koriste potencije broja 2, ili prosti brojevi. Na primjer, često korištena vrijednost, koja nudi dobre mogućnosti, je prost broj 2³¹-1. Osim "slučajnosti" brojeva, može se promatrati i pojave u bitovnim zapisima dobivenih brojeva. Katkad se mogu primjetiti ponavljanja najnižih bitova, što treba izbjegavati. Za veličinu X₀ najčešće se koristi neka veličina dobivena od sistemskog sata u računalu. Ali problem seed-a općenito je mnogo opširniji, te će o njemu biti više napisano kasnije. Broj a mora biti neparan, a poželjno je da bude unutar nekoliko redova veličine od vrijednosti broja m. Važno je napomenuti da ukoliko se koriste veliki brojevi, treba koristiti veličine bez predznaka, da bi se izbjegla moguća promjena predznaka u zapisu cijelog broja u dvojnom komplementu.

Vrlo bitno svojstvo ovakvih brojeva, a i jedan od najjednostavnijih kriterija kvalitete generatora slučajnih brojeva, jest prosječna vrijednost svih brojeva, koja mora biti što bliža polovici od gornje granice intervala slučajnih brojeva.

1-1-2. Lagged Fibonacci generator

Ovakvi generatori dobili su svoje ime zbog sličnosti formule s rekurzivnom formulom kojom se dobivaju brojevi Fibonaccijevog niza. U daljnjem tekstu ce ovakvi generatori biti označeni oznakom LFG. Opći oblik formule za dobivanje brojeva na ovakav način glasi:

X_n = X_n-l + X_n-k (mod m)

s time da brojevi l i k moraju biti u odnosu l > k > 0. Ovakvi generatori pseudoslučajnih brojeva postaju sve zanimljiviji, jer su u nekim svojstvima značajno bolji od LCG. Period niza brojeva dobivenih ovako nije ograničen brojem m. Broj m se odabire kao potencija broja 2, jer je ta kombinacija dosta testirana. Problem ponavljanja nižih bitova se može pojaviti kod malih vrijednosti brojeva l i k, ali ovo se može lako izbjeći. Poput LCG-a i ovaj postupak zahtjeva malo računanja, te uzima malo procesorskog vremena, jedino što zahtjeva pamćenje zadnjih l vrijednosti. Bitno je naglasiti da barem jedan od tih l brojeva na samom početku mora biti neparan. LFG imaju i bolja svojstva kad im se vrijednosti koriste u n-torkama.

1-1-3. Linear shift register generator

Ova skupina generatora ima sličnosti s prethodnim, ali se brojevi ne ostvaruju aritmetičkim operacijama, nego operacijama logičkog posmaka ulijevo i isključivog ili, barem u ovom slučaju. Shema koja prikazuje kako bi ovo trebalo funkcionirati uzeta je iz dokumenta RFC1750 :

+----+     +----+     +----+                      +----+
| B  | <-- | B  | <-- | B  | <--  . . . . . . <;--| B  | <-+
|  0 |     |  1 |     |  2 |                      |  n |   |
+----+     +----+     +----+                      +----+   |
  |                     |            |                     |
  |                     |            V                  +-----+
  |                     V            +----------------> |     |
  V                     +-----------------------------> | XOR |
  +---------------------------------------------------> |     |
                                                        +-----+

Najniži bit se postavlja kao parni paritet prethodnog broja, nad kojim je eventualno izvrsena operacija logičke konjukcije sa odabranom "maskom". I ovo predstavlja zanimljivu mogućnost generiranja pseudoslučajnih brojeva, te ju se eventualno može i koristiti u kombinaciji s dvije već predložene klase generatora.

1-2. Ostale mogućnosti za ostvarivanje slučajnosti

Metode koje će se ovdje raspravljati katkada i izlaze iz okvira pseudoslučajnosti, ali svatko kome je u interesu dobivati kvalitetne količine slučajnih brojeva, mora biti upoznat i s alterativama. Bilo bi to lijepo kada bi na računalu postojao neki modul koji bi davao slučajne brojeve koji su prikupljeni iz istinski stohastičkih događaja koji se događaju na mikro razini, i uz odgovarajuću programsku podršku, nebi nas brinula nikakva pseudoslučajnost. Makar danas i postoje hardverska rješenja koja se bave ovim problemom, ona su rijetka pa se ovdje tek spominju. Ovisno o samom računalu i njegovoj funkciji, nude se neke dodatne mogućnosti dobivanja slučajnih brojeva.

1-2-1. Hardverske mogućnosti

Prva mogućnost jest sistemski sat i stvari koje on može mjeriti. Ovo rješenje koristi standrad ISO C prilikom inicijalizacije svog generatora slučajnih brojeva. Ovo rješenje se može smatrati lakim i kvalitetnim, ali u sigurnostnoj upotrebi se pokazuje kao vrlo manjkavo. O tim manjkavostima biti će pisano kasnije. Makar ga se koristi najčešće samo za inicijalizaciju, može ga se koristiti da za direktno dobivanje slučajnih brojeva u manjim opsezima.

Drugo rješenje, koje zadire u zonu stohastičkih procesa, jest korištenje audio ulaza na zvučnoj kartici, ako je računalo posjeduje. "Sisanjem" sirovih kvantiziranih vrijednosti s tog ulaza u trenutku kada ne prima nikakav signal, dobiva se samo šum, koji je zbiljska slučajna pojava. Eventualno se problem krije u amplitudi šuma, tj. opsegu vrijednosti koje se dobijaju, ali iz duljeg niza bitova koji dođu iz tog ulaza se mogu dobiti slučajni brojevi zadovoljavajućih svojstava.

Treće rješenje, ma koliko bilo blisko, to zapravo i nije. Radi se o pojedinačnim pristupnim vremenima prilikom rada sa hard diskom. Prilikom pristupanja podatcima na disku, događaju se razne fluktuacije smera kretanja zraka u disku, pa se vremena pristupanja razlikuju skoro svaki put. Pod pretpostavkom da postoji hardver koji takva vremena mjeri i način da se programski pristupi tim vrijednostima, na raspolaganju imamo prilično dobar izvor slučajnosti unutar računala.

Još jedna od korištenih mogućnosti bi recimo mogla biti brojanje vremena između klikova mišem ili tipkovnicom, ili mjerenje kretanja miša. Ova mogućnost nije za odbaciti, ali treba biti oprezan, pošto takve veličine mogu biti manje slučajne nego što si mi to mislimo, zbog tendencije da se pokreti, ili intervali klikova, ponavljaju.

1-2-2. "Žvakanje velikih količina podataka

Na velikim računalima, poslužiteljima raznih funkcija i na višekorisničkim sustavima, stvaraju se velike količine privremenih podataka, koji ubrzo bivaju spremljeni ili prebrisani. Iz tih podataka se može, nekim manje ili više složenim postupkom, složiti nizove slučajnih bitova zadovoljavajuće kvalitete. U ovu svrhu se mogu koristiti hash funkcije, razni algoritmi za enkripciju ili sažimanje. Ovo rješenje je pogodno za velika računala koja kroz sebe provrte velike količine podataka, dok je nije preporučljivo korisititi na jednokorisničkim sustavima. Također, treba naglasiti da se za takvo dobivanje slučajnih brojeva trebaju koristiti podatci koji su lokalni za to računalo, odnosno podatci koji nisu vidljivi izvana.

2. Posebnosti vezane uz generiranje pseudoslučajnih brojeva

Ovisno o mjestu korištenja generatora slučajnih brojeva, nad njima se postavljaju zahtjevi. Za generatore pseudoslučajnih brojeva u simulacijama se zahtjevaju dobra statistička svojstva, neprimjetnost ili nepostojanje grupiranja n-torki koje nastaju od elemenata niza pseudoslučajnih brojeva nastalih tim generatorom. Pošto se u tu svrhu treba generirati puno slučajnih brojeva, sama procedura generiranja smije trošiti samo mali dio procesorskog vremena. Pošto se danas takve simulacije često vrte na sustavima s više procesora, zanimljivo je pogledati kako se generatori pseudoslučajnih brojeva implementiraju na takvim sustavima.

S druge strane, generatori pseudoslučajnih brojeva često su korišteni u raznim sigurnosnim sustavima. Takvi sigurnosni sustavi ne smiju imati slabosti, pa tako niti generator pseudoslučajnih brojeva ne smije biti slabost. Prilikom stvaranja ili korištenja generatora pesudoslučajnih brojeva stoga treba imati na umu što sve mogu iskoristiti oni koji žele probiti u sigurnosni sustav, što ima je sve na raspolaganju, i na što sve treba paziti.

2-1. Generatori pseudoslučajnih brojeva u višeprocesorskim sustavima

Zbog toga što se u višeprocesorskim sustavima u jednom trenutku izvodi više procesa koji u nekom trenutku mogu zahtjevati generiranje slučajnog broja, implementacija generatora je znatno složenija. Treba nam mogućnost raspoređivanja generiranih brojeva, ali uz zadržavanje kvaliteta slučajnosti nizova i njihove reproducibilnosti. Postoji nekoliko načina rješavanja ovog problema.

2-1-1. Centralizirani pristup

Centralizirani pristup je implementiran preko jedne zadaće ili procesa od kojeg drugi zahtjevaju slučajne brojeve. Ovime se izbjegava stvaranje više nizova slučajnih brojeva, ali je slabost ovog pristupa pad preformansi izvršavanja ukupne simulacije. Javlja se i problem reprodukcije nizova, pošto se brojevi djele onako kako zahtjevi stignu, što se ne mora svaki put dogoditi na isti način. Zbog ovog razloga i rezultati mogu varirati od simulacije do simulacije.

2-1-2. Repliciranje generatora

Repliciranje generatora podrazumjeva stvaranje generatora za svaki zadatak koji se izvršava. Generatori mogu, ali i ne moraju imati isti seed, već se mogu koristiti jedinstveni seed-ovi, recimo identifikacijski broj zadatka. Ovakav pristup ne garantira neovisnost nizova generiranih brojeva, a i mogu nastati problemi s korelacijom. Najvažnija prednost ovog pristupa jest efikasnost, pa stoga je pogodan u nekim primjenama.

2-1-3. Distribuirani pristup

Prethodna dva primjera nisu pretjerano teški za implementaciju, ali pate od nedostataka koji im smanjuju domenu u kojoj se mogu koristiti. U ovom slučaju se također za svaki zadatak stvara posebni generator pseudoslučajnih brojeva, ali njihovi seed-ovi nastaju od jednog generatora. Zbog toga je analiza olakšana, te je lakše promatrati i statističke osobine nizova.

Primjer ovakvog pristupa jest metoda "slučajnog stabla" (The Random tree method). Za potrebe implementacije ovakvog pristupa koriste se dva LCG-a :

L_k+1 = a_LL_k (mod m)

R_k+1 = a_RR_k (mod m)

Generator R se stvori za svaki zadatak koji ga zatraži, a seed mu je sljedeći element iz niza koji generira generator L, kako je skicirano na slici.

Dobra strana ove metode jest da su nastali nizovi reproducibilni, te da nisu centralizirani, odnosno ponavljani. Ovo je bitno u slučajevima kada se traži dinamičko nastajanje generatora. Loša strana jest ta što nema garancije da se dva niza, pošto se radi o LCG, neće preklopiti. Također će dva niza sa vrlo sličnim seed-ovima biti slični. Ovo se može izbjeći ili barem ulažiti korištenjem velikog perioda generatora, ali to nije garancija.

2-2. Zanimljivosti iz perspektive sigurnosti i kriptografije

Sigurnost neke poruke proizlazi iz mogućnosti da se ona dobro kriptira, tako da bude nerazumljiva bilo kome osim onome kome treba biti razumljiva. Enkripcija počiva na upotrebi ključeva, simetričnih ili asimetričnih, a te ključeve generira računalo u najvećem broju slučajeva. Pošto računalo najčešće koristi neki postupak koji počiva na pseudoslučajnosti, postoji vrlo mala ili ipak malo veća mogućnost rekonstrukcije generiranja pseudoslučajnih brojeva, čime se omogućuje ugrožavanje sigurnosti kriptiranih podataka.

Korištenje u računalo ugrađenog sata je prilično slabo rješenje za odabiranje seed-a generatora, pošto se tako nastali niz slučajnih brojeva može lako rekonstruirati ako se zna na kojem je računalu niz nastao i otprilike u koje doba. Ove činjenice se možda ne čine tako očitima, ali netko kome je to posao bi se potrudio. Također nije dobro koristiti serijske brojeve raznih CD-a ili drugih proizvoda, jer se i njih dade doznati, ili u najgorem slučaju protivnik ima generator tih ključeva pa može ispitivati mogućnosti.

Vezano za problem nastajanja slučajnih brojeva, bitan je podatak o količini informacija u mogućem nastalom broju. Na primjer, ako 50 bitne brojeve dobivamo fiksnom operacijom nad 20 bitova, protivnik, uz uvjet da je upoznat s postupkom nastanka, ne mora pogađati 2⁵⁰ vrijednosti, nego 2²⁰. Uz to, ukupna entropija, odnosno neuređenost, niza kojeg generira neki generator pseudoslučajnih brojeva, ovisi o umnošku vjerojatnosti pojedinog broja i logaritma te vjerojatnosti. Ako je raspodjela vjerojatnosti uniformna po cijelom području iz kojeg su generirani brojevi, tada će entropija biti najveća. Ako je raspodjela neuniformna, entropija pada, te potencijalni protivnik može početi od područja koja su vjerojatnija.

Iz toga razloga loše koristiti nizove znakova iz neke baze koja uglavnom sadrži riječi i slova, poput prometa nekog Usenet servera, jer oni sadrže manje informacije, odnosno slučajnosti, nego što bi se to moglo pomisliti. Iz ovog razloga je bolje koristiti zapise koji nisu riječi nekog jezika, nego su nekakvi drugačiji podatci. Također, za veću količinu "slučajnosti", odnosno entropije, poželjno je te podatke obraditi na taj način da se dobije manje bitova, ali s većom slučajnošću po bitu.

3. Primjeri implementacije

U sklopu ovog seminarskog rada nastala je i biblioteka sa nekoliko funkcija za generiranje slučajnih brojeva. Slijedi dokumentacija tih funkcija. Sve funkcije su razrađene i testirane na operativnom sustavu Linux Red Hat 6.2.

unsigned int sndrnd_l();
unsigned long long sndrnd_ll();

Ove dvije funkcije se razlikuju zapravo samo u tipu podatka koji vraćaju. Da bi se dobili slučajni bitovi pomoću ovih funkcija, koristi se /dev/audio uređaj sa kojega se, kada ništa nije uključeno u ulaze na zvučnoj kartici, mogu očitavati stanovite male promjene razine. Čitanjem 8-bitnih podataka sa tog uređaja najčešće se dobiva broj 127, ali samo iznimno 126. Da bi se od ovakve pojave izolirao jedan bit slučajnosti, čitaju se parovi tih 8-bitnih podataka, i na mjestu na kojem se detektira promjena zabilježi se 1, a inače 0. Bitovi tako dobivenog niza se čitaju u parovima, te se za kombinaciju 01 u izlaznu riječ unese 0, a za kombinaciju 10, u izlaznu riječ ide 1. Nakon dovoljno pokušaja, popuni se 32-bitna ili 64-bitna riječ. Valja naglasiti da novije Linux jezgre(kerneli) samostalno održavaju uređaje(devices) za generiranje slučajnih brojeva. Iz objektivnih razloga ovdje se ova mogućnost samo spominje.

Zamjećeni problemi ovakvog pristupa generiranju slučajnih brojeva jesu sporost procesa, pošto su te promjene rjetke, pa se treba čekati puno da bi se dočekala nova slučajna riječ. Problem je zapažen i u tome da se katkada ulaz na zvučnoj kartici zaglavi na nekoj konstantnoj vrijednosti, što onemogućuje generiranje slučajnih bitova na ovaj način u to vrijeme.

Ovakav generator brojeva se može koristiti samostalno, ili za davanje seed-a drugim generatorima.

unsigned int LCG();

Ova je funkcija implementacija LCG(16807,0,2³¹ - 1, X₀), gdje postoji više načina za dobivanjem toga početnog X₀. Na samom početku on ima vrijednost 1. Seed se može dobiti bilo pomoću već navedene funkcije sndrnd_l, funkcijom

void init_LCG();

ili se može dobiti "ručnim" unošenjem seed-a pomoću funkcije

void seed_LCG(unsigned int);.

Za bilježenje stanja LCG-a koristi se varijabla LCG_var, do koje korisnik nema direktnog pristupa, već se mora koristiti gorenavedenim funkcijama.

Ovakav generator je brz, zauzima malo memorije, ali zato ima najviše ograničenja, u pogledu perioda i nepredvidljivosti brojeva.

unsigned int hash_rnd();

Ova funkcija se ponaša slično kao i funkcija sndrnd_l, samo što se ulazni podatci dobivaju iz datoteke. Iz datoteke se čitaju bitovi, i na analogan način se iz njih generiraju pseudoslučajni brojevi. Da bi se mogla koristiti ova funkcija, potrebno je koristiti jos dvije druge funkcije

void init_hash_rnd(char *);
void stop_hash_rnd();

od kojih se pomoću prve zadaje ime datoteke iz koje će se vaditi bitovi, a pomoću druge pravilno zatvaramo datoteku onda kad smo s njom gotovi. Ako prilikom čitanja datoteke, funkcija naiđe na kraj datoteke, ona će tada početi čitati istu tu datoteku, ali od početka.

Ovakav pristup nije bez koristi, ali je problem da bi se za ozbiljnu upotrebu podatci trebali još bolje iskorištavati. Ova funkcija zahtjeva i rad s diskom, što je čini značajno sporijom. Kvaliteta dobivenih brojeva ovisi o metodi vađenja sažetka a i o sadržaju datoteke. Na primjer, bolje je koristiti binarne formatizirane datoteke nego tekstualne.

unsigned int LFG();

Ova je funkcija implementacija LFG(55,24,31), što simbolizira ovkovu formulu X_n = X_n-l + X_n-k (mod m), gdje su l = 24, k = 55, a m = 2³¹ -1. Da bi ovakav generator dobro radio, umjesto jedne memorijske lokacije za pohranu prethodne vrijednosti koje koristi LCG, ovakav generator ih zahtjeva 55. Tih 55 vrijednosti treba postaviti prije pokretanja generatora. Za tu svrhu su raspoložive funkcije

void init_LFG(); void h_init_LFG();

od kojih prva koristi sndrnd_l funkciju za dobivanje potrebnih brojeva, dok druga koristi hash_rnd funkciju koja bi vec trebala biti inicializirana.

Sam spremnik je pohranjen u varijabli unsigned int LFG_polje[55], dok se za prolazak kroz to polje koristi varijabla unsigned int LFG_brojac, pomoću koje se određuju koji elementi se zbrajaju i i na koje mjesto u tom polju treba zapisati novoizračunati broj.

Period ovakovog generatora je čak veći od 2⁸⁰, i općenito ima bolja svojstva od LCG-a. Jedini je problem što zahtjeva više memorije za pohranu svih potrebnih podataka. Takodjer je i vrlo brz, jer je za izračun potrebno samo jedno zbrajanje i jedna modulo operacija. Također, potrebno je znati više od trenutnog stanja da bi se pomoću formule mogao izračunati sljedeći element.

Sve ove funkcije su definirane unutar datoteke myrndlib.c, dok se header datoteka za ove funkcije zove myrndlib.h.

Literatura:

D. Eastlake 3rd, S. Crocker, J. Schiller : RFC1750 - "Randomness Recommendations for Security", 1994.

I. Foster : "Designing and Building Parallel Programs", 1995.
http://www-unix.mcs.anl.gov/DBPP/TEXT/book.html

Clark Haass: "Increase Data Protection with the Hardware-Based Intel(r) Random Number Generator", 2000.
http://developer.intel.com/update/ARCHIVE/ISSUE22/STORIES/TOP5.HTM
Članak o hardverskom generatoru slučajnih brojeva na Intel(r) čipsetu 810

Verena M. Umar : "Random Number Generators", 1995.
http://csep1.phy.ornl.gov/CSEP/RN

Robert Uzgalis : "Random Numbers, Encryption, and Hashing", 1995.
http://www.serve.net/BUZ/Notes.1st.year/HTML/C6/RAND.000.html

Paul Coddington : "Random Number Generator Library", 1996.
http://nhse.npac.syr.edu/RANDOM