Suita NIST SP 800-22

Cele 15 teste statistice de aleatorism. Fiecare se ruleaza pe o secventa lipita sau prin API, cu acelasi contract. Testul spectral (DFT) este cel tratat in profunzime - cu referat, controverse si simulari.

#1 · Frecventarulabil

Frequency (Monobit)

Verifica daca proportia de 1 si 0 este apropiata de 1/2 pe toata secventa.

#2 · Frecventarulabil

Frequency within a Block

Verifica daca proportia de 1 este apropiata de 1/2 in fiecare bloc de M biti.

#3 · Runsrulabil

Runs

Numara secventele maximale de biti identici (runs) si le compara cu asteptarea.

#4 · Runsrulabil

Longest Run of Ones in a Block

Compara cea mai lunga succesiune de 1 din fiecare bloc cu distributia asteptata.

#5 · Algebra liniararulabil

Binary Matrix Rank

Verifica dependentele liniare intre subsiruri de lungime fixa, prin rangul unor matrice peste GF(2).

#6 · Spectralrulabil

Discrete Fourier Transform (Spectral)

Detecteaza componente periodice in domeniul frecventei. Testul tratat in profunzime aici.

#7 · Templaterulabil

Non-overlapping Template Matching

Numara aparitiile non-suprapuse ale unui sablon dat si le compara cu asteptarea.

#8 · Templaterulabil

Overlapping Template Matching

Ca testul anterior, dar potrivirile pot fi suprapuse.

#9 · Compresierulabil

Maurer's Universal Statistical

Estimeaza compresibilitatea: o secventa aleatoare nu poate fi comprimata semnificativ.

#10 · Complexitaterulabil

Linear Complexity

Lungimea celui mai scurt LFSR care genereaza secventa (prin Berlekamp-Massey).

#11 · Tiparerulabil

Serial

Verifica daca toate tiparele de m biti (suprapuse) apar cu frecvente egale.

#12 · Tiparerulabil

Approximate Entropy

Compara frecventa tiparelor de lungime m si m+1; aleator => entropie aproape maxima.

#13 · Mers aleatorrulabil

Cumulative Sums (Cusum)

Masoara cat de departe ajunge mersul aleator al sumelor partiale de +/-1.

#14 · Mers aleatorrulabil

Random Excursions

Numara vizitele la fiecare stare in ciclurile mersului aleator (stari -4..-1, 1..4).

#15 · Mers aleatorrulabil

Random Excursions Variant

Varianta: numarul total de vizite la 18 stari (-9..-1, 1..9) in tot mersul.