TestU01

TestU01 er en statistisk empirisk testpakke implementeret i ANSI C , der giver et sæt hjælpeprogrammer til test af tilfældige talgeneratorer . Den seneste version af biblioteket blev introduceret i 2007 af Pierre L'Ecuyer og Richard Simard fra University of Montreal [1] .

Pakken indeholder flere typer PRNG'er , herunder nogle foreslået i litteraturen og nogle meget brugt i software . Det giver generelle implementeringer af klassiske statistiske test for tilfældige talgeneratorer, såvel som dem, der er foreslået i litteraturen og nogle originale. Disse tests kan anvendes på generatorer, der allerede er i biblioteket, brugerdefinerede generatorer og tilfældige talstrømme. Specielle tests tester alle sekvenser af ensartet fordelte tilfældige tal i eller bitsekvenser. Grundlæggende værktøjer til at konstruere punktvektorer genereret af generatorer er også til stede [1] . $[0,1]$

Historie [1]

TestU01 blev først implementeret i 1985 i Pascal og indeholdt test foreslået af Donald Knuth i anden udgave af andet bind af The Art of Programming [2] . Fire år senere blev det genimplementeret i Modula-2- sproget som en pakke med et modulært design . Derefter blev nogle af de mest brugte PRNG'er tilføjet sammen med nye tests. Mellem 1990 og 2001 blev pakken med jævne mellemrum opdateret med nye generatorer og test, og brugermanualen blev opdateret rettidigt (på fransk). moduler, der indeholder værktøjer til at teste familier af generatorer, blev først introduceret i 1997. I 2002 redesignede Pierre L'Ecuyer og Richard Simard biblioteket, implementerede det i C og oversatte manualen til engelsk. $f$

PRNG-kvalitetskriterier

PRNG'er er hovedsageligt designet til godt at simulere en sekvens af uafhængige tilfældige variabler , normalt i et reelt interval eller i et binært sæt . I det første tilfælde siger hypotesen 0 A , at tallene 0 , 1 , 2 , 3 ... er uafhængige størrelser fra en ensartet fordeling i intervallet [3] . I den anden siger 0 B , at der er en sekvens af uafhængige tilfældige bit, som hver antager værdien eller med lige stor sandsynlighed [3] . $(0,1)$ $[0,1]$ $\mathrm{H}$ $u$ $u$ $u$ $u$ $(0,1)$ $\mathrm{H}$ $0$ $en$

$\mathrm{H}$ 0 A svarer til at sige, at for enhver heltal ervektor ( 0 , ...,) ensartet fordelt i endimensionel terning. For algoritmiske PRNG'er er udsagnet falsk, fordi vektorerne i dem tager deres værdier fra et endeligt antalalledimensionellevektorer, som generatoren er i stand til at producere [3] . $t$ $u$ $u$ $t-1$ $t$ $(0,1)$ $t$ $\psi$ $t$ $t$

For en sekvens af bit kan hypotesen 0 B heller ikke formelt kaldes sand i det tilfælde, hvor længden af sekvensen overstiger antallet af bits af generatortilstande, fordi antallet af mulige sekvenser, der produceres, ikke kan overstige [3] . Generatorens opgave er at sikre, at sekvenserne i felten af alle mulige sekvenser i . $\mathrm{H}$ $t$ $b$ $2$ $b$ $2$ $t$

Et andet kvalitetskriterium for PRNG bruges i kryptologi og spillemaskiner. Her er der udover alt det ovenstående særligt opmærksom på uforudsigeligheden af efterfølgende numre [3] .

Funktioner [1]

TestU01 tilbyder fire grupper af moduler til at arbejde med generatorer:

implementering af en forprogrammeret generator (modul ); $u$
implementering af særlige statistiske test (modul ); $s$
implementering af statistiske testbatterier (modul ); $b$
anvendelse af test på hele familier af generatorer (modul ). $f$

Når en bestemt test anvendes på outputtet af en størrelsesgenerator , forbliver testens p - værdi normalt rimelig, indtil størrelsen af dataene når en vis værdi . Derefter divergerer p - værdien til eller med en eksponentiel hastighed. Modulet giver forskeren mulighed for at udforske forholdet mellem en specifik test og strukturen af et sæt punkter opnået ved hjælp af en specifik familie af generatorer. Denne teknik kan bruges til at bestemme størrelsen af de data, der skal testes, afhængigt af længden af generatorens periode, før generatoren begynder at systematisk fejle testene. $n$ $n_{0}$ $0$ $en$ $f$

TestU01 tilbyder flere testbatterier såsom SmallCrush (bestående af 10 test), Crush (96 test) og BigCrush (106 test). På en Pentium 4 -baseret computer med et Linux -operativsystem , for en simpel generator, tager batterilevetiden for SmallCrush-tests flere minutter, Crush - omkring en time, BigCrush - omkring et dusin timer [3] .

Andre programmer til test af PRNG

En af de meget brugte PRNG-testpakker er DIEHARD [4] , som indeholder en lang række statistiske test, men har en række ulemper og begrænsninger. For det første er rækkefølgen af tests såvel som deres parametre (såsom prøvestørrelse osv.) fastsat, hvilket har en dårlig effekt på testhastigheden [3] . For det andet kræver DIEHARD 32-bit heltal skrevet i binært som input , mens mange generatorer producerer tal mindre end 32 bit [3] . Sammenlignet med TestU01 er DIEHARD-pakken mindre fleksibel i disse aspekter [3] .

En anden offentlig testpakke er SPRNG [5] biblioteket , som inkluderer de klassiske tests beskrevet i The Art of Programming [2] . National Institute of Standards and Technology har også udviklet sit eget sæt af 15 tests til test af generatorer, der bruges i kryptografi [6] .

Batterier

Alphabit- batteriet blev skabt til at teste hardwaregeneratorer til tilfældige tal . Udfører ni på hinanden følgende test, før hver omskrivning af inputdataene.

Kanin er et batteri, der fokuserer mere på at teste binære data , men nogle tests består med faste parametre, uanset hvor stort inputtet er. Derfor fører data større end 64 megabyte til en fejl i en af testene og fører til overløb af RAM . [7]

SmallCrush , et lille og hurtigt batteri af test, læser generatoren som en fil, der indeholder flydere i . Filgrænsen er lige under 51320000 tilfældige tal. Filen vil blive overskrevet i begyndelsen af hver test. Nogle test kræver, at generatoren returnerer mindst 30 bits opløsning, ellers er det meget sandsynligt, at generatoren fejler dem. Bruges normalt til at kontrollere gennemførligheden af at teste på mere stringente batterier [7] . $[0,1)$

Crush - Et batteri af strenge statistiske tests. Indeholder både de klassiske Knuth-tests og mange andre. Nogle af disse tests forudsætter, at generatoren returnerer mindst 30 bits opløsning, ellers vil testene mislykkes. En af testene kræver 31 bit data. Batteriet bruger cirka 2 35 tilfældige tal [7] .

BigCrush er et batteri af de mest stringente statistiske tests. Som med andre batterier kræver nogle tests mindst 30 bit input, ellers mislykkes testene. Også en af testene kræver 31 bit data. Batteriet bruger næsten 238 tilfældige tal. Da BigCrush først dukkede op, havde selv PRNG'er, der blev betragtet som gode, svært ved at komme forbi det [7] .

SmallCrush Battery Tests

Her er nogle eksempler på SmallCrush batteritests [1] .

Fødselsdag Spasings	En test baseret på fødselsdagsparadokset . Der vælges tilfældige punkter på et stort interval, hvorimellem afstandene skal være asymptotisk Poisson-fordelte .
hul	En test, der bruges til at bestemme intervallet mellem gentagelser af samme ciffer.
CouponCollector	Lad en sekvens af længden n og dimensionere m. Vi studerer sekvenser af en vis længde, der indeholder et m-bit tal. $\xi _{1},\xi _{2},\dots ,\xi _{n}$
MatrixRank	Testen vælger et bestemt antal bits fra et bestemt antal tilfældige tal for at danne en matrix over {0,1}. Derefter bestemmes matrixens rang.

Litteratur

Pierre L'Ecuyer, Richard Simard. TestU01: AC-bibliotek til empirisk testning af tilfældige talgeneratorer. — D'epartement d'Informatique et de Recherche Op'erationnelleUniversit'e de Montr'eal: ACM Transactions on Mathematical Software, 2007. — 40 s.
Knuth D.E. The Art of Computer Programming bind 2, - ISBN 0-201-89684-2 .

Noter

↑ 1 2 3 4 5 Pierre L'Ecuyer, Richard Simard. TestU01: AC-bibliotek til empirisk testning af tilfældige talgeneratorer // ACM Trans. Matematik. Softw .. - August 2007. - T. 33 , no. 4 . — S. 22:1–22:40 . — ISSN 0098-3500 . doi : 10.1145 / 1268776.1268777 .
↑ 12 D.E. Knuth. The Art of Computer Programming, bind 2: Seminumeriske algoritmer . - Addison-Wesley, 1981. - 142 s. Arkiveret 4. september 2008 på Wayback Machine
↑ 1 2 3 4 5 6 7 8 9 Pierre L'Ecuyer og Richard Simard. Et softwarebibliotek i ANSI C til empirisk test af tilfældige talgeneratorer . - 2013. - S. 219. Arkivkopi dateret 9. december 2014 på Wayback Machine
↑ Marsaglia . ] DIEHARD: et batteri af tilfældighedstest (downlink) . Institut for Statistik (1996). Arkiveret fra originalen den 20. januar 2016. (ubestemt)
↑ M. Mascagni og A. Srinivasan. Algoritme 806: SPRNG: Et skalerbart bibliotek til generering af pseudorandomtal // ACM-transaktioner på matematisk software. - 2000. - 1. december ( bind 26 , nr. 4 ). — S. 436–461 .
↑ CSRC - NIST SP 800-22: Dokumentation og software . csrc.nist.gov. Hentet 24. september 2017. Arkiveret fra originalen 25. september 2017. (ubestemt)
↑ 1 2 3 4 TestU01 resultater - BitBabbler . www.bitbubbler.org Hentet 26. september 2017. Arkiveret fra originalen 6. oktober 2017.