Генераторы псевдослучайных чисел и методы их тестирования — страница 8

интерпретируются человеком, поэтому на их основе выводы могут быть неоднозначными.   4.2 Статистические тесты В отличие от графических тестов, статистические тесты выдают численную характеристику последовательности и позволяют однозначно сказать, пройден ли тест. Наиболее известные тесты: §        Подборка статистических тестов Д. Кнута; §        DIEHARD; §        CRYPT-X;

§        NIST STS; 4.2.1 Основные принципы Зная вероятностные свойства истинно случайной последовательности, можно на их основе проверять гипотезу о том, на сколько сгенерированная последовательность похожа на случайную. Для этого для каждого теста подбирается подходящая статистика, вычисляется её значения для идеальной и сгенерированной последовательности. Если разность этих значений превышает некоторое

критическое значение, установленное заранее, то последовательность считается неслучайной. Для „хороших“ последовательностей вероятность такого события крайне мала(допустим ~0,001 и обозначим её α). Однако, существует вероятность того, что „плохая“ последовательность удовлетворит критерию и будет сделан вывод о ее случайности(обозначим вероятность такого события β). На практике значения длины

последовательности n, α и β связаны, задается α и подбирается n такое, чтобы минимизировать β. Определим величину P-value как вероятность того, что идеальный генератор сгенерировал последовательность менее случайную, чем исследуемый. Тогда если P-value больше α, то исследуемая последовательность считается случайной и наоборот в противном случае. Кратко шаги статистического тестирования можно изобразить в виде таблицы:

4.2.2 Тесты Д. Кнута Тесты Кнута основаны на статистическом критерии χ2[2]. Вычисляемое значение статистики χ2 сравнивается с табличными результатами, и в зависимости от вероятности появления такой статистики делается вывод о ее качестве. Среди достоинств этих тестов — небольшое их количество и существование быстрых алгоритмов выполнения. Недостаток — неопределенность в трактовке результатов. Вот краткое описание этих

тестов: 1.      Проверка несцепленных серий. Последовательность разбивается на m непересекающихся серий и строится распределение χ2 для частот появления каждой возможной серии. 2.      Проверка интервалов. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя длины подпоследовательностей, все элементы которых принадлежат определенному числовому