9346692692

2 Testowanie generatorów liczb pseudlosowych

2.1    Przypadek czy korelacja?

W tym rozdziale zajmiemy się podstawowym zagadnieniem związanym z generatorami liczb pseudolosowych — testowaniem ich. Jak ważne jest to zagadnienie niech uzmysłowi fakt, że nie ma możliwości określenia czy mamy do czynienia z sekwencją losową, a jedynie zaproponować testy, po przejściu których możemy tylko jej nie odrzucić.

2.2    Podstawowe testy

Test częstości jest jednym z podstawowych. Polega on na sprawdzeniu częstości występowania zer i jedynek w ciągu bitów: gdzie uq i ni są odpowiednio ilością zer i jedynek. Test ten spełnia rozkład x² z jednym stopniem swobody dla długości sekwencji n > 10 (w praktyce musi być n 10000). Oczywiście w najlepszym wypadku no & ni.

Dwubitowy test to rozwinięcie poprzedniego — sprawdza częstości występowania par 00, 01, 10 i 11 (które powinny być notabene w przybliżeniu równe). Gdy no i ni zdefiniujemy jak poprzednio, a noo + noi + wio + odpowiednio częstością powyższych par to test wygląda następująco:

Statystyka ta spełnia rozkład y² dla 2 stopni swobody (n > 21).

Test pokerowy jest nieco bardziej skomplikowany⁶. Otóż definiujemy k takie, że n/k > 5(2^fc), wtedy l = n/m. Dzielimy ciąg na sekwencje nie zachodzące na siebie, każda o długości k i oznaczamy przez n* częstość występowania i -tej (1 < i < 2^k). Test ten ustala czy powyższe ciągi o długości k występują z równym prawdopodbieństwem zgodnie ze statystyką

która spełnia rozkład y² z 2^k — 1 stopniami swobody.

Jest uogólnionym testem częstości.

(3)