Надежность двухуровневого подхода к тестированию в наборе тестов NIST SP 800-22
Рассматривается предложенный в наборе тестов NIST SP 800-22 двухуровневый подход к тестированию генераторов случайных чисел, который состоит в подсчете количества последовательностей, прошедших основной тест, и проверке распределения p-значений с помощью хи-квадрат-теста. Данный подход может повысить надежность статистического теста, однако он чувствителен к погрешностям аппроксимации, возникающим при вычислении p-значений. Показано, что для последовательностей, порождаемых с помощью симметричного алгоритма блочного шифрования (AES), двухуровневый подход к тестированию не является надежным. Систематическая погрешность при вычислении p-значений зависит только от погрешности аппроксимации точного распределения статистики эквивалентным ему теоретическим распределением и от числа бит n в тестируемых последовательностях. Для надежного двухуровневого тестирования такая погрешность не должна превосходить σN = 1kk - 1 N , где σ = 1k( 1 - 1k )N – стандартное отклонение от среднего числа частиц в ячейке в равновероятной схеме размещения N частиц по k ячейкам. Подобные эвристические соображения и проведенные эксперименты позволяют предположить, что, например, при n = 220 в двухуровневом частотном тесте (Frequency test) из набора тестов NIST SP 800-22 количество тестируемых последовательностей N не должно превышать 26 000. Для полного исключения систематической погрешности, возникающей при проведении частотного теста и определении номера ячейки из k возможных ячеек (непересекающихся подынтервалов отрезка [0, 1]), которому принадлежит p-значение, предложены двусторонние оценки квантилей биномиального закона. , number=1, journal=Журнал Белорусского государственного университета. Математика. Информатика, author=Серов, Александр Александрович, year=2026, month=июн., pages=22–35