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

интервалу. 3.      Проверка комбинаций. Последовательность разбивается на подпоследовательности определенной длины, и исследуются серии, состоящие из различных комбинаций чисел. 4.      Тест собирателя купонов. Пусть ξ1,ξ2...ξn — последовательность длиной n и размерности m. Исследуются подпоследовательности определенной длины, содержащие каждое m-разрядное число. 5.      Проверка

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

последовательности. 4.2.3 Пакет статистических тестов NIST Данный программный пакет разработан Лабораторией информационных технологий (англ. Information Technology Laboratory), являющейся главной исследовательской организацией Национального института стандартов и технологий (NIST). В его состав входят 15 статистических тестов, целью которых является определение случайного характера бинарных последовательностей, вообще говоря, произвольной

длины, порожденных либо аппаратными, либо программными генераторами случайных или псевдослучайных чисел. Эти тесты основаны на различных особенностях присущих только непроизвольным последовательностям. 1.      Частотный побитовый тест Суть данного теста заключается в определении соотношения между нулями и единицами во всей двоичной последовательности. Цель — выяснить действительно ли число нулей и единиц в

последовательности приблизительно одинаковы, как это можно было бы предположить в случае истинно случайной бинарной последовательности. Тест оценивает насколько близка доля единиц к 0,5. Таким образом число нулей и единиц должно быть примерно одинаковым. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является истинно случайной. В противном случае, последовательность носит

случайный характер. Стоит отметить, что все последующие тесты проводятся при условии, что пройден данный тест. 2.      Частотный блочный тест Суть теста — определение доли единиц внутри блока длиной m бит. Цель — выяснить действительно ли частота повторения единиц в блоке длиной m бит приблизительно равна m/2, как можно было бы предположить в случае абсолютно случайной последовательности. Вычисленное в ходе теста