Теория
Статистические тесты не доказывают случайность — они ищут закономерности, которых не должно быть у честного ГПСЧ, и возвращают p-value: вероятность увидеть такое же или большее отклонение случайно. Порог обычно \(\alpha = 0{,}05\): p меньше — «отвергается», больше — «не отвергается».
Частотный тест сравнивает наблюдаемые частоты с ожидаемыми критерием \(\chi^2 = \sum \frac{(O_i - E_i)^2}{E_i}\); серийный делает то же для пар подряд идущих значений. Runs-тест считает серии значений выше/ниже медианы, автокорреляция — корреляцию последовательности с собственной копией, сдвинутой на лаг. Энтропия Шеннона показывает, насколько полно используется диапазон.
Важно: выводы тестов надёжны только на длинных выборках: при N < 50 случайный разброс огромен. И ни один набор тестов не заменит криптографический анализ.
Пример с решением
- Условие. Последовательность 5, 5, 5, 5, 5 в диапазоне 0…9: частотный тест.
- Формула. \(\chi^2 = \sum \frac{(O_i - E_i)^2}{E_i}\), \(E = N/10 = 0{,}5\).
- Подстановка. Одно значение встретилось 5 раз, девять — ни разу.
- Вычисление. \(\chi^2 = (5-0{,}5)^2/0{,}5 + 9 \cdot (0-0{,}5)^2/0{,}5 = 45\), df = 9.
- Ответ. \(p \approx 0\) — случайность отвергается: константа не похожа на выход ГПСЧ.
Главное
- p-value — вероятность отклонения у честного ГПСЧ; порог \(\alpha = 0{,}05\).
- Тесты отсеивают закономерности, но не доказывают случайность.
- N ≥ 50 — минимальная разумная выборка.