Условия надежности двухуровневого подхода к тестированию в наборе тестов NIST SP800-22

Рассматривается двухуровневый подход к оценке качества генераторов случайных чисел, предложенный в батарее тестов NIST SP 800-22, который состоит в вычислении частот $p$-значений, попавших в $k=10$ равных интервалов отрезка $[0,1]$, и проверке их распределения на равномерность с помощью критерия согласия Пирсона.
Такой подход может повысить надежность теста, однако он оказывается чувствительным к погрешностям аппроксимации, возникающим при вычислении $p$-значений. Показано, что для последовательностей, порождаемых с помощью симметричного алгоритма блочного шифрования AES, двухуровневый подход к тестированию не является надежным. Систематическая погрешность при вычислении $p$-значений зависит от точности аппроксимации допредельных распределений статистики их предельным распределением при стремлении объема $n$ выборки к бесконечности. Для надежности двухуровневого тестирования такая погрешность не должна превосходить $\sigma/N = \frac{1}{k}\sqrt{ \frac{k - 1}N}$, где $\sigma =\sqrt{\frac1k\left(1-\frac1k\right)N}$ — стандартное отклонение от среднего числа $\frac{N}k$ частиц в ячейке в равновероятной схеме распределения $N$ частиц ($p$-значений) по $k$ ячейкам. Такие эвристические соображения и проведенные эксперименты позволяют предположить, что, например, при $n=2^{20}$ в тесте второго уровня Частотного теста из набора тестов NIST SP 800-22 количество тестируемых последовательностей $N$ не должно превышать $26000$.
Предложены двусторонние оценки квантилей биномиального закона применение которых совместно с универсальными неравенствами для функции распределения биномиального закона позволяет полностью исключить систематическую погрешность, возникающую при проведении Частотного теста и определении чисел $p$-значений, оказавшихся в каждом подынтервале из $k$ возможных непересекающихся подынтервалов отрезка $[0,1]$.