NIST SP 800-22 · 15 teste implementate
Suită completă de teste de aleatorism NIST SP 800-22
Toate cele 15 teste statistice ale suitei, rulate pe binarul C++ real - din interfață sau prin API-ul public. Testul spectral (Transformată Fourier Discretă) este tratat în profunzime, cu referat, controverse și simulări Monte-Carlo.
Cele 15 teste
Toate testele ->#1 · Frecvențărulabil
Frequency (Monobit)
Verifică dacă proporția de 1 și 0 este apropiată de 1/2 pe toată secvența.
#2 · Frecvențărulabil
Frequency within a Block
Verifică dacă proporția de 1 este apropiată de 1/2 în fiecare bloc de M biți.
#3 · Runsrulabil
Runs
Numără secvențele maximale de biți identici (runs) și le compară cu așteptarea.
#4 · Runsrulabil
Longest Run of Ones in a Block
Compară cea mai lungă succesiune de 1 din fiecare bloc cu distribuția așteptată.
#5 · Algebră liniarărulabil
Binary Matrix Rank
Verifică dependențele liniare între subșiruri de lungime fixă, prin rangul unor matrice peste GF(2).
#6 · Spectralrulabil
Discrete Fourier Transform (Spectral)
Detectează componente periodice în domeniul frecvenței. Testul tratat în profunzime aici.
#7 · Templaterulabil
Non-overlapping Template Matching
Numără aparițiile non-suprapuse ale unui șablon dat și le compară cu așteptarea.
#8 · Templaterulabil
Overlapping Template Matching
Ca testul anterior, dar potrivirile pot fi suprapuse.
#9 · Compresierulabil
Maurer's Universal Statistical
Estimează compresibilitatea: o secvență aleatoare nu poate fi comprimată semnificativ.
#10 · Complexitaterulabil
Linear Complexity
Lungimea celui mai scurt LFSR care generează secvența (prin Berlekamp-Massey).
#11 · Tiparerulabil
Serial
Verifică dacă toate tiparele de m biți (suprapuse) apar cu frecvențe egale.
#12 · Tiparerulabil
Approximate Entropy
Compară frecvența tiparelor de lungime m și m+1; aleator => entropie aproape maximă.
#13 · Mers aleatorrulabil
Cumulative Sums (Cusum)
Măsoară cât de departe ajunge mersul aleator al sumelor parțiale de +/-1.
#14 · Mers aleatorrulabil
Random Excursions
Numără vizitele la fiecare stare în ciclurile mersului aleator (stări -4..-1, 1..4).
#15 · Mers aleatorrulabil
Random Excursions Variant
Variantă: numărul total de vizite la 18 stări (-9..-1, 1..9) în tot mersul.
Tratat în profunzime
Testul spectral (DFT)
Testul din secțiunea 2.6 mută secvența în domeniul frecvenței și numără câte vârfuri spectrale depășesc pragul de 95%. Este și cel mai contestat test din suită: documentația NIST raportează N1 = 46 pentru exemplul de 100 de biți, dar codul de referință și o transformată corectă dau N1 = 48. Aici îl tratăm în detaliu - matematica, implementarea, simulările Monte-Carlo și controversa.