Pod pojmom ispitivanja generatora, misli se na ispitivanje kvalitete generiranog niza. Pri ispitivanju se želi ustanoviti pokazuje li generirani niz ili ne neke poželjne karakteristike (npr. nedostatak pravilnosti u nizu, ispravna distribucija brojeva i sl.). Cilj ispitivanja je iz beskonačnog skupa testova (tj. beskonačnog skupa karakteristika niza) izvući bitne testove. Postoji mnoštvo različitih skupova testova, ali niti jedan ne može proglasiti niz generiranih brojeva “slučajnim”, moguće je samo zaključiti pokazuje li niz neka od ponašanja koja bi pokazao niz generiran od strane idealnog generatora (idealni generator je npr. čovjek koji baca potpuno simetrični novčić). Nasuprot tome, na temelju rezultata se može sigurno zaključiti da neki niz nije slučajan tj. da generator radi neispravno. Npr. ako generator generira niz u kojem su svi brojevi isti, očito je da se ne radi o slučajnim brojevima.

Osnova za ispitivanje je statistički test tvrdnje. Prije ispitivanja, postavlja se nulta tvrdnja (H₀) te alternativna tvrdnja (H_a). Pri ispitivanju generatora slučajnih brojeva, tvrdnje imaju slijedeći oblik:

• H₀: niz koji se ispituje je niz slučajnih brojeva
• H_a: niz koji se ispituje nije niz slučajnih brojeva

Za svaki ispit potrebno je odrediti statističku vrijednost koja se ispituje tj. vrijednost pomoću koje se odlučuje koja od tvrdnji se prihvaća kao istinita (uvijek se prihvaća točno jedna od navedenih tvrdnji). Nakon toga, potrebno je teoretski, matematičkim postupcima, odrediti očekivani rezultat nulte tvrdnje u uvjetima normalne, referentne raspodjele. Nakon toga se određuje kritična vrijednost za koju se ne očekuje da će se premašiti u uvjetima normalne raspodjele (tj. mala je vjerojatnost da će se dogoditi taj slučaj). Konačno, na temelju generiranog niza se računa tražena statistička vrijednost. Ako mjerena vrijednost prelazi teoretski određen prag, može se sa određenom sigurnošću reći da generirani niz nije niz slučajnih brojeva (prihvaćanje H_a). Vrijedi i obratno tj. ako mjerena vrijednost ne prelazi određeni prag, moguće je sa određenom sigurnošću prihvatiti H₀. Mjera sigurnosti s kojom se generator prihvaća ili ne prihvaća kao ispravan se naziva nivo značaja a . Ako je a prevelik, ispitivanje može odbaciti niz koji u stvarnosti je niz slučajnih brojeva. Obratno, ako je a premali, ispitivanje može prihvatiti niz koji u stvarnosti nije niz slučajnih brojeva. Tipično se vrijednost a uzima između 0.001 i 0.05. U ovdje spomenutim ispitivanjima, a će iznositi 0.01 (tipično za kriptografske primjene). To znači da se niz može prihvatiti ili odbaciti sa 99% sigurnosti ili drugim riječima, rezultat ispita će dovesti do krivog zaključka u 1% slučajeva (pod ovime se ne misli da će od sto ispitivanja istog niza jedno ispitivanje dati pogrešan rezultat, nego da će se pogrešan zaključak izvesti nad jednim od sto mogućih kombinacija niza slučajnih brojeva). Tipično se u ispitima upotrebljavaju dvije standardne raspodjele: normalna raspodjela (očekivana raspodjela promatranih vrijednosti u nekom prostoru) te c ² raspodjela (očekivana raspodjela učestalosti pojave nekih događaja). Ako ispitani niz nije niz slučajnih brojeva, mjerena statistička vrijednost ispita će se nalaziti u ekstremnim dijelovima krivulje (veličina tih dijelova ovisi o odabranoj vrijednosti a ). Odabir raspodjele ovisi o karakteristici koja se ispituje, a dodatno je u posebnim ispitivanja moguće uzeti i neku drugu raspodjelu. Sam tijek ispitivanja zahtjeva generiranje velikog niza brojeva (barem 10³ brojeva u nizu, a tipično oko 10⁶ brojeva).

Važno je istaknuti da svaki ispit mjeri neku od poželjnih karakteristika slučajnih brojeva (npr. ravnomjerna raspodjela brojeva u prostoru). Nakon serije ispitivanja u najboljem slučaju moguće je zaključiti da ispitivani generator posjeduje željena svojstva te da bi mogao biti dobar generator slučajnih brojeva (čak i tako neodređen zaključak se može izvući sa 99% sigurnosti). S druge strane moguće je zaključiti da ispitivani generator nije odgovarajući (također sa 99% sigurnosti).

Poželjno je nakon provedene serije statističkih ispita izvršiti dodatna eksperimentalna ispitivanja. Tipični primjer je upotreba generatora u simulaciji čiji rezultati se mogu a priori teoretski odrediti: simulacijom se računa neka vrijednost te se uspoređuje sa izračunatom teoretskom vrijednosti.

U nastavku će biti prikazan skup ispita koju preporučuje NIST (National Institute of Standards and Technology). Algoritmi za pojedine ispite su navedeni u odgovarajućoj NIST dokumentaciji (2.) zajedno sa pripadnim formalnim matematičkim izvodim te ovdje neće biti prikazani.

Nivo značaja u svim ispitima iznosi 0.01, a poželjno je da se niz sastoji od barem 100 brojeva. Svi ispiti se vrše nad nizom bitova, ali izvedeni zaključci se normalno mogu primjeniti za generator slučajnih brojeva. Već je ranije spomenuto da se generator slučajnih brojeva dobije jednostavnim grupiranjem više bitova iz niza slučajnih bitova.

Ispitivanje učestalosti u nizu

Promatrana karakteristika u ovom ispitu je odnos jedinica i nula u nizu bitova. Svrha je uočiti da li je u promatranom ispitu približno jednak broj jedinica i nula. Naravno, za očekivati je da kvalitetni generator slučajnih bitova daje približno jednak broj jedinica i nula. Sva druga ispitivanja ovise o prolazu ovog ispita. Može se reći da je prolaz ovog ispita nužan, ali ne i dovoljan uvjet za donošenje zaključka radi li se o nizu slučajnih bitova ili ne.

Ispitivanje učestalosti u bloku

Promatrana karakteristika u ovom ispitu je odnos jedinica i nula u M-bitnim blokovima u nizu. Svrha je uočiti je li broj jedinica i nula podjednak u svakom M-bitnom bloku. Za blok veličine M=1 ovaj ispit se pretvara u ispit učestalosti u nizu.

Ispitivanje uzastopnih ponavljanja istih bitova u nizu

Promatrana karakteristika u ovom ispitu je ukupni broj uzastopnih ponavljanja jednog broja u niz. Uzastopno ponavljanje je pojava dva ili više istih brojeva za redom. Svrha je uočiti da li se broj uzastopnih ponavljanja sa očekivanim brojem koji bi bio u savršeno slučajnom nizu

Ispitivanje najdužeg uzastopnog ponavljanja jedinica u bloku

Promatrana karakteristika u ovom ispitu je najduže uzastopno ponavljanje jedinica u M-bitnim blokovima. Svrha je odrediti da li se dužina najdužeg uzastopnog ponavljanja poklapa sa dužinom koja bi se očekivala u nizu slučajnih bitova. Nepravilnost u dužini najdužeg uzastopnog ponavljanja jedinica u bloku povlači za sobom i nepravilnost u dužini najdužeg uzastopnog ponavljanja nula u bloku, pa nije potrebno obaviti posebno ispitivanje za ponavljanje nula u M bitnim blokovima. Veličina bloka M se bira u ovisnosti o veličini niza n, prema tablici koju preporučuje NIST.

Ispitivanje ranga matrice

Promatrana karakteristika u ovom ispitu je rang matrica koje se dobiju iz podniza ispitivanog niza. Namjera je ustanoviti postoji li linearna ovisnost između podnizova fiksne duljine u ispitivanom nizu.

Spektralno ispitivanje

Promatrana karakteristika u ovom ispitu su amplitude u diskretnoj Fourierovoj transformaciji promatranog niza. Svrha ispita je otkrivanje periodičkih pojava u promatranom nizu (ponavljajući uzorci koji su međusobno “previše blizu”) koje bi ukazale na odstupanja od niza slučajnih bitova.

Ispitivanje ponavljanja predloška u generiranom nizu

Promatrana karakteristika u ovom ispitu je broj ponavljanja unaprijed određenog niza bitova (predloška) u generiranom nizu. Preveliki broj ponavljanja predloška ukazuje na pravilnost u generiranom nizu bitova, te potencijalno lošu distribuciju brojeva koji se dobiju grupiranjem bitova (kada se želi ostvariti niz slučajnih brojeva). Ispit se javlja u dvije varijante: sa preklapanjem (overlapping) i bez preklapanja (non-overlapping). U varijanti sa preklapanjem, dopušteno je da se uzorci međusobno preklapaju (npr. broj ponavljanja predloška 101 u nizu 1010101 iznosi tri). Obratno, u varijanti bez preklapanja to nije dopušteno (za isti primjer, broj ponavljanja iznosi dva: 1010101).

Maurerov univerzalni statistički test

Promatrana karakteristika u ovom ispitu je broj bitova između istih uzoraka (mjera koja određuje koliko se niz može komprimirati). Svrha ispita je ispitati da li se promatrani niz može značajno komprimirati bez gubitaka informacije. Za niz koji se može značajno komprimirati smatra se da nije niz slučajnih bitova zbog činjenice da je kompresija niza (bez gubitaka) efikasnija ukoliko niz pokazuje periodička svojstva,

Ispitivanje na temelju Lempel-Ziv kompresije

Promatrana karakteristika u ovom ispitu je broj različitih uzoraka (riječi) u ispitivanom nizu na temelju koje se određuje može li se niz značajnije komprimirati ili ne.

Ispitivanje linearne složenosti

Promatrana karakteristika u ovom ispitu je veličina posmačnog registra s povratnom vezom. Ispitivani niz se dijeli na blokove te se za svaki M-bitni blok računa minimalna veličina posmačnog registra s povratnom vezom koji generira sve bitove u tom bloku. Za niz slučajnih bitova se očekuju veće veličine posmačnog registra s povratnom vezom.

Ispitivanje preklapajućih uzoraka

Promatrana karakteristika u ovom ispitu je učestalost pojave svih mogućih m-bitnih uzoraka (uz preklapanje) u cijelom ispitivanom nizu. Namjera je otkriti da li je broj pojava 2^m m-bitnih preklapajućih uzoraka približno jednak broju koji se očekuje za niz slučajnih brojeva. Niz slučajnih brojeva bi trebao imati ravnomjernu raspodjelu, tj. očekuje se da je vjerojatnost pojave svih m-bitnih uzoraka jednaka. Za m=1 ovaj ispit prelazi u ispit učestalosti u nizu.

Ispitivanje približne entropije

Promatrana karakteristika u ovom ispitu je također učestalost pojave svih mogućih preklapajućih m-bitnih uzoraka u nizu. Namjera je usporediti učestalost preklapajućih blokova susjednih veličina (m-bitni i m+1-bitni blok) sa očekivanim rezultatima.

Ispitivanje kumulativne sume

Promatrana karakteristika u ovom ispitu je najveće odstupanje od nule kumulativne koja se dobije postepenim zbrajanjem članova modificiranog niza. Modificirani niz dobije se tako da sve nule u ispitivanom nizu poprime vrijednost -1. Namjera je ustanoviti je li najveće odstupanje preveliko ili premalo u odnosu na očekivano.

Ispitivanje slučajnog hoda

Slučajni hod na temelju kumulativne sume dobije se nakon što se sve nule u nizu zamijene sa vrijednosti –1. Prolaskom kroz bitove promatranog niza računa se suma. Trenutna vrijednost u nekom koraku označava stanje. Ciklus u slučajnom hodu sastoji se od niza koraka koji počinju i završavaju na istom mjestu. Korak je u stvari promjena sume za +/- 1 pri računanju sume za sljedeći bit u nizu. Svrha ispita je odrediti da li broj “posjeta” svakom stanju u jednom ciklusu značajno odstupa od očekivanog broja za niz slučajnih bitova. Dodatna varijanta ovog ispita za karakteristiku uzima broj koliko je neko stanje posjećeno u slučajnom hodu kroz cijeli niz (a ne kroz ciklus).