A NIST Statistical Tests egy statisztikai tesztcsomag , amelyet az Information Technology Laboratory fejlesztett ki, a National Institute of Standards and Technology (NIST) fő kutatószervezete . 15 statisztikai tesztből áll, amelyek célja a hardveres vagy szoftveres véletlenszám-generátorok által generált bináris sorozatok véletlenszerűségének mértékének meghatározása . Ezek a tesztek különféle statisztikai tulajdonságokon alapulnak, amelyek egyediek a véletlenszerű szekvenciákra.
Ennek a tesztnek az a lényege, hogy meghatározzuk a nullák és egyesek közötti kapcsolatot a teljes bináris sorozatban. A cél annak kiderítése, hogy a sorozat nullák és egyesek száma megközelítőleg ugyanannyi-e, mint ahogyan azt egy valóban véletlenszerű bináris sorozat esetén feltételezhetjük. A teszt azt értékeli, hogy az egységek aránya mennyire közelíti meg a 0,5-öt. Így a nullák és egyesek számának megközelítőleg azonosnak kell lennie. Ha a teszt során számított valószínűségi érték p < 0,01, akkor ez a bináris sorozat nem igazán véletlenszerű. Ellenkező esetben a sorrend véletlenszerű. Érdemes megjegyezni, hogy minden további tesztet azzal a feltétellel hajtanak végre, hogy ezt a tesztet sikeresen teljesítik.
A teszt lényege, hogy meghatározzuk az egységek arányát egy m bit hosszúságú blokkon belül . A cél annak kiderítése, hogy egy m bites blokkban az egyesek ismétlődési gyakorisága megközelítőleg egyenlő-e m / 2-vel, ahogy azt egy teljesen véletlenszerű sorozat esetén feltételezhetjük. A vizsgálat során számított p valószínűségi értéknek legalább 0,01-nek kell lennie. Ellenkező esetben ( p < 0,01) a bináris sorozat nem igazán véletlenszerű. Ha elfogadjuk, hogy m = 1, akkor ez a teszt az 1. tesztbe kerül (frekvencia bitteszt).
A lényeg az, hogy megszámoljuk az eredeti sorozat sorainak teljes számát, ahol a "sor" szó azonos bitek folyamatos részsorozatát jelenti. Egy k bit hosszúságú sorozat k abszolút azonos bitből áll , és egy ellentétes értéket tartalmazó bittel kezdődik és végződik. Ennek a tesztnek az a célja, hogy megállapítsa, hogy a különböző hosszúságú egyesekből és nullákból álló sorok száma valóban megfelel-e azok számának véletlenszerű sorrendben. Különösen gyorsan vagy lassan határozza meg az egyesek és nullák váltakozását az eredeti sorrendben. Ha a teszt során számított valószínűségi érték p < 0,01, akkor ez a bináris sorozat nem igazán véletlenszerű. Ellenkező esetben a sorozat véletlenszerűnek tekinthető.
Ez a teszt meghatározza a leghosszabb 1-es sort egy m bites blokkon belül . A cél annak kiderítése, hogy egy ilyen sorozat hossza valóban megfelel-e a leghosszabb sorozatok hosszára vonatkozó elvárásoknak egy teljesen véletlenszerű sorozat esetén. Ha a teszt során számított p < 0,01 valószínűségi értéket feltételezzük, hogy az eredeti sorozat nem véletlenszerű. Ellenkező esetben azt a következtetést vonják le, hogy véletlenszerű. Meg kell jegyezni, hogy az egyesek és nullák körülbelül azonos előfordulási gyakoriságának feltételezéséből ( 1. teszt ) az következik, hogy ennek a tesztnek pontosan ugyanazokat az eredményeit kapjuk, ha a leghosszabb nullák sorozatát vesszük figyelembe. Ezért a méréseket csak mértékegységekkel lehet elvégezni.
Itt az eredeti bináris sorozatból felépített, nem metsző részmátrixok rangsorai kerülnek kiszámításra . Ennek a tesztnek az a célja, hogy tesztelje az eredeti sorozatot alkotó fix hosszúságú részkarakterláncok lineáris függését. Ha a teszt során számított valószínűségi érték p < 0,01, akkor következtetést vonunk le a bemeneti bitsorozat nem véletlenszerűségére. Egyébként teljesen véletlenszerűnek tekintjük. Ez a teszt a DIEHARD csomagban is megtalálható .
A teszt lényege, hogy megbecsüljük az eredeti sorozat diszkrét Fourier-transzformációjának csúcsainak magasságát . A cél a bemeneti sorozat periodikus tulajdonságainak azonosítása, például egymáshoz közel elhelyezkedő ismétlődő szakaszok. Ez tehát egyértelműen mutatja a vizsgált szekvencia véletlenszerű természetétől való eltéréseket. Az ötlet az, hogy a 95%-os amplitúdóküszöböt meghaladó csúcsok száma jóval 5% felett van. Ha a teszt során számított valószínűségi érték p < 0,01, akkor ez a bináris sorozat nem teljesen véletlenszerű. Ellenkező esetben véletlenszerű.
Ez a teszt megszámolja az eredeti sorozatban található előre meghatározott minták számát. A cél az, hogy azonosítsák azokat a véletlenszerű vagy pszeudo-véletlen számgenerátorokat, amelyek túl gyakran generálnak nem periodikus mintákat. Mint a 8. tesztben az átfedő minták egyeztetésére , egy m bit hosszúságú ablakot is használunk az m hosszúságú minták keresésére . Ha nem található minta, az ablak egy bittel eltolódik. Ha a minta megtalálható, az ablak a talált mintát követő bitre ugrik, és a keresés folytatódik. A vizsgálat során számított p valószínűségi értéknek legalább 0,01-nek kell lennie. Ellenkező esetben ( p < 0,01) a bináris sorozat nem teljesen véletlenszerű.
Ennek a tesztnek az a lényege, hogy megszámolja az eredeti sorozatban található előre meghatározott minták számát. Mint a 7. tesztben a nem átfedő minták illesztésére , egy m bit hosszúságú ablakot is használunk meghatározott m hosszúságú minták keresésére . Maga a keresés is hasonló módon történik. Ha nem található minta, az ablak egy bittel eltolódik. Az egyetlen különbség ez a teszt és a #7 teszt között az , hogy ha a mintát megtaláljuk, az ablak csak egy kicsit előre mozdul, utána a keresés folytatódik. A vizsgálat során számított p valószínűségi értéknek legalább 0,01-nek kell lennie. Ellenkező esetben ( p < 0,01) a bináris sorozat nem teljesen véletlenszerű.
Ez határozza meg a bitek számát a forrássorozat azonos mintái között (egy olyan mérték, amely közvetlenül kapcsolódik a tömörített sorozat hosszához). A teszt célja annak kiderítése, hogy egy adott sorozat információvesztés nélkül jelentősen tömöríthető-e. Ha meg lehet csinálni, akkor nem igazán véletlen. A teszt során kiszámítjuk a p valószínűségi értéket . Ha p < 0,01, akkor feltételezzük, hogy az eredeti sorozat nem véletlenszerű. Ellenkező esetben azt a következtetést vonják le, hogy véletlenszerű.
A teszt a lineáris visszacsatolásos eltolási regiszter ( LFSR ) működési elvén alapul . A cél annak kiderítése, hogy a bemeneti sorozat elég összetett-e ahhoz, hogy teljesen véletlenszerűnek lehessen tekinteni. Az abszolút véletlenszerű sorozatokat hosszú lineáris visszacsatolásos eltolási regiszterek jellemzik. Ha egy ilyen regiszter túl rövid, akkor feltételezzük, hogy a sorozat nem teljesen véletlenszerű. A teszt során kiszámítjuk a p valószínűségi értéket . Ha p < 0,01, akkor feltételezzük, hogy az eredeti sorozat nem véletlenszerű. Ellenkező esetben azt a következtetést vonják le, hogy véletlenszerű.
Ez a teszt abból áll, hogy megszámoljuk az összes lehetséges, m bit hosszúságú átfedő minta frekvenciáját az eredeti bitsorozaton. A cél annak meghatározása, hogy a 2 m -es, m bit hosszúságú átfedő minták előfordulási száma megközelítőleg ugyanannyi-e, mint egy teljesen véletlenszerű bemeneti bitsorozat esetén. Ez utóbbinak, mint tudod, egységessége van, vagyis minden m bit hosszúságú minta azonos valószínűséggel jelenik meg a sorozatban. Ha a teszt során számított valószínűségi érték p < 0,01, akkor ez a bináris sorozat nem teljesen véletlenszerű. Ellenkező esetben véletlenszerű. Érdemes megjegyezni, hogy m =1 esetén a periodicitásteszt frekvencia bitenkénti tesztté alakul (1. sz.).
A periodicitásteszthez hasonlóan ez a teszt is az eredeti bitsorozat m bit hosszúságú minták összes lehetséges átfedésének gyakoriságának megszámlálására összpontosít. A teszt célja az eredeti sorozat két egymást követő m és m + 1 hosszúságú blokkjának átfedési frekvenciáinak összehasonlítása hasonló blokkok átfedési frekvenciáival egy teljesen véletlenszerű sorrendben. A vizsgálat során számított p valószínűségi értéknek legalább 0,01-nek kell lennie. Ellenkező esetben ( p < 0,01) a bináris sorozat nem teljesen véletlenszerű.
A teszt egy tetszőleges bejárás során a maximális eltérésből (nullától) áll, amelyet a sorozat adott (-1, +1) számjegyeinek összesített összege határoz meg. Ennek a tesztnek az a célja, hogy megállapítsa, hogy a bemeneti szekvenciában előforduló részsorozatok kumulatív összege túl nagy-e vagy túl kicsi-e ahhoz képest, hogy egy ilyen összeg egy teljesen véletlenszerű bemeneti szekvenciánál várható. Így a kumulatív összeg tetszőleges bejárásnak tekinthető. Véletlenszerű sorozat esetén a tetszőleges sétától való eltéréseknek nullához közel kell lenniük. Egyes típusú sorozatok esetében, amelyek nem teljesen véletlenszerűek, a nullától való ilyen eltérések egy tetszőleges bejárás során meglehetősen jelentősek. Ha a teszt során számított valószínűségi érték p < 0,01, akkor a bemeneti bináris sorozat nem teljesen véletlenszerű. Ellenkező esetben véletlenszerű.
Ennek a tesztnek az a lényege, hogy a kumulatív összeg tetszőleges bejárása során megszámolja azoknak a ciklusoknak a számát, amelyeknek pontosan k látogatása van. A halmozott összeg tetszőleges lépése a sorozat (0,1) utáni részösszegekkel kezdődik, amelyeket a megfelelő sorozatra fordítunk (-1, +1). A véletlenszerű bejárási ciklus egységnyi hosszúságú lépések sorozatából áll, amelyeket véletlenszerű sorrendben hajtanak végre. Ezenkívül egy ilyen bejárás ugyanazon az elemen kezdődik és végződik. Ennek a tesztnek az a célja, hogy megállapítsa, hogy a hurkon belül egy bizonyos állapotba tett látogatások száma eltér-e egy teljesen véletlenszerű bemeneti szekvencia esetén hasonló számtól. Valójában ez a teszt nyolc tesztből áll, amelyet mind a nyolc ciklusállapotban végeznek el: -4, -3, -2, -1 és +1, +2, +3, +4. Minden ilyen tesztben a következő szabály szerint döntenek a kezdeti sorozat véletlenszerűségi fokáról: ha a teszt során számított valószínűségi érték p < 0,01, akkor a bemeneti bináris sorozat nem abszolút véletlenszerű. Ellenkező esetben véletlenszerű.
Ez a teszt az összesített összeg tetszőleges bejárásával számolja meg az adott állapotba tett látogatások teljes számát. A cél az, hogy egy tetszőleges bejárás során meghatározzuk a különböző államok látogatásainak várható számától való eltéréseket. A valóságban ez a teszt 18 tesztből áll minden állapothoz: -9, -8, ..., -1 és +1, +2, ..., +9. Minden szakaszban következtetést vonunk le a bemeneti sorozat véletlenszerűségéről. Ha a teszt során számított valószínűségi érték p < 0,01, akkor a bemeneti bináris sorozat nem teljesen véletlenszerű. Ellenkező esetben véletlenszerű.