Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 21
Текст из файла (страница 21)
В процессетеста определяется, согласуется ли количество блоков, содержащих максимальные серии определенной длины, с ожидаемым для случайных последовательностей значением.Отметим, что отклонения в распределении единичных серий влекутза собой отклонения в распределении нулевых серий, поэтому достаточноосуществить только один из двух тестов.-137Длина последовательности п должна быть не менее 128 бит.Binary Matrix Rank Test.Объектом исследования является ранг двоичных матриц, образованных непересекающимися подпоследовательностями последовательности ё.Тест направлен на выявление линейной зависимости между подпоследовательностями фиксированной длины.
Отметим, что он также входит в наборDIEHARD [51].Длина последовательности ё должна быть не менее 38 912 бит.Discrete Fourier Transform (Spectral) Test.Объектом исследования является спектр последовательности, полученный при помощи дискретного преобразования Фурье. В частности,определяется отклонение числа спектральных компонентов, амплитуда которых превышает 95% барьер, от ожидаемого результата 5%. Целью тестаявляется выявление периодичности (т.е.
повторяющихся шаблонов).Рекомендуется использовать последовательности ё длиной не менее1000 бит.Non-overlapping Template Matching Test.Объектом исследования является количество повторений определенной фиксированной подпоследовательности (шаблона) в исходной последовательности. Целью теста является выявление генераторов псевдослучайных чисел, порождающих последовательности со слишком часто встречающимися апериодическими шаблонами.Для поиска шаблона длины т используется скользящее m-битное окно.
Если шаблон не обнаружен, окно перемещается на одну позицию; впротивном случае осуществляется сдвиг окна на т позиций.Процедура тестирования осуществляется для каждого апериодического шаблона указанной длины (в реализации тестов NIST шаблоны задаютсяв текстовых файлах). Таким образом, в результате теста получается наборр-значений — по одному для каждого шаблона (при т = 9 возможно получение до 148 значений, при т = 10 —до 284).Реализация тестов NIST рассчитана на поиск шаблонов длиной ,от 2до 10 бит.
Рекомендуемыми значениями для 777. являются 8 и 9.Overlapping Template Matching Test.-138Объектом исследования является количество повторений определенной фиксированной подпоследовательности (шаблона) в исходной последовательности. Целью теста является выявление генераторов псевдослучайных чисел, порождающих последовательности со слишком часто встречающимися апериодическими шаблонами.Для поиска шаблона длины т используется скользящее m-битное окно. В отличие от теста Non-overlapping Template Matching Test, окно всегда сдвигается на одну позицию независимо от того, был обнаружен шаблонили нет.Длина исследуемой последовательности должна составлять не менее610 бит.
Размер шаблона т рекомендуется выбирать равным 9 или 10.Maurer's Universal Statistical Test.Тест был разработан Ули Маурером [57] в начале 1990-х гг.Объектом исследования является количество бит, находящихся между повторяющимися шаблонами в последовательности. Тест позволяет оценить, насколько может быть сжата последовательность без потерь информации. Последовательности, допускающие значительное сжатие, признаются неслучайными.Длина исследуемой последовательности должна составлять не менее387840 бит.Linear Complexity Test.Объектом исследования является линейная сложность последовательности, т.е.
наименьшая длина регистра сдвига с линейными обратнымисвязями, порождающего последовательность. Тест позволяет определить,соответствует ли линейная сложность ожидаемому для случайных последовательностей значению. Последовательности, обладающие слишком низкойлинейной сложностью, признаются неслучайными.'Длина исследуемой последовательности п должна составлять не менее610 бит (п ^ 106). Длина подпоследовательности должна выбираться такимобразом, чтобы выполнялись соотношения 500 ^ М ^ 5 000 и N — \j^\ ^200.Serial Test.Объектом исследования является количество вхождений всех возмож--139ных m-битных пересекающихся шаблонов в последовательность.
Тест позволяет определить, соответствует ли наблюдаемое число вхождений каждого из 2т шаблонов ожидаемому. Для случайных последовательностейожидается, что все шаблоны являются равновероятными, т.е. встречаютсяс равной частотой.Как и в тесте Overlapping Template Matching Test, для поиска: вхождений; шаблонов в последовательность используется скользящее окно, на ..каждом; шаге сдвигающееся на одну позицию.В^результате теста вычисляются два р-значения:Длина исследуемой последовательности п и размер шаблона т долж- ..ны выбираться таким образом, чтобы выполнялось соотношение m<|_log2:nJ - 2 ,Approximate Entropy Test.Объектом исследования является число< вхождений-всех возможных -.m-битных пересекающихся шаблонов.
в последовательность. Целью тестаявляется сравнение разницы количества вхождений; шаблонов длины т и. т-+ 1 с ожидаемым:для случайных последовательностей.значением^Длина последовательности п и размер шаблонам должны выбиратьсятаким образом, чтобы.выполнялось соотношение m < [Iog 2 nJ —5.Cumulative Sums (Cusum) Test.Объектом исследования являются максимальные отклонения от нулевого значения частичных сумм преобразованных членов последовательности^ полученных из исходных членов путем замены 0-1-> —1, It-» 1. Цельютеста является выявление последовательностей; в которых частичные суммы отклоняются от нулевого значениязначительно сильнее, чем ожидаетсядля случайной последовательности;В результате теста вычисляются два.р-значения: одно при проходе попоследовательности от начала к концу, а второе — вобратном направлении.Длина исследуемой последовательности должна быть не менее 100 бит.Random Excursions Test.В данном тесте последовательность частичных сумм рассматриваетсякак маршрут случайных блужданий по неориентированному графу.
Значение частичной суммы рассматривается в качестве номера вершины графа.-140Объектом исследования является количество циклов, содержащих определенные вершины ровно К раз (под циклом в тесте понимается последовательность вершин маршрута, первый и последний элементы которой равнынулю, а все остальные являются ненулевыми). Целью теста является выявление последовательностей, в которых количество вхождений вершин вциклы значительно отличается от ожидаемого для случайной последовательности значенияВ результате теста вычисляется восемь значений достигаемого уровнязначимости.Длина исследуемой последовательности должна быть не менее 1 0 6 бит.Random Excursions Variant Test.В этом тесте, как и в предыдущем, последовательность частичныхсумм рассматривается как маршрут случайных блужданий по неориентированному графу, представленный номерами вершин.
Объектом исследования является количество проходов маршрута через различные вершины.В результате теста формируется 18 р-значений, соответствующих различным вершинам.Длина исследуемой последовательности должна быть не менее 1 0 6 бит.4.2.2. Р Е А Л И З А Ц И Я Н А Б О Р А С Т А Т И С Т И Ч Е С К И Х Т Е С Т О В NISTНациональный институт стандартов и технологии разработал программный комплекс Assess, реализующий набор статистических тестов,рассмотренных в предыдущем разделе.
Описание программного комплекса приведено в [63], а сам программный комплекс доступенти Интернет по адресу:в сеhttp://csrc.nist.gov/groups/ST/toolki't/rng/documents/sts-2.1.zip.Поскольку статистические тесты носят вероятностный характер, ,неверно делать вывод о качестве генератора псевдослучайных последовательностей на основании исследования лишь одной последовательности.Поэтому программный комплекс рассчитан на автоматизированное тестирование определенной выборки двоичных выходных последовательностей,полученных при различных начальных состояниях генератора.
Д л я получения достоверных результатов рекомендуется использовать выборки объ--141ема 1000 и более.Входными данными для программного комплекса являются:1) файл, содержащий полученные при помощи исследуемого генераторапсевдослучайные последовательности;2) количество последовательностей в файле;3) длина каждой последовательности в битах;4) подмножество тестов, которые будут применяться для исследованияпоследовательности;5) параметры тестов.Заключение о качестве генератора основывается на двух параметрах:- относительном количестве последовательностей, проходящих тест (т.
е.отношении числа прошедших тест последовательностей к общему ихколичеству);- равномерности распределения р-значений, полученных для различных <последовательностей.Для оценки соответствия относительного количества последовательностей, прошедших тест, ожидаемому для случайных последовательностейзначению вычисляется доверительный интервал, зависящий от объема выборки и выбранного уровня значимости.Для оценки равномерности распределения р-значений (которые, напомним, являются значениями вероятности) интервал [0; 1] разбивается надесять равных непересекающихся подинтервалов, и подсчитывается числовхождений р-значений в подинтервалы.
Для полученных значений вычисляется статистика хи-квадрат, после чего определяется достигаемый уровень значимости, отражающий равномерность распределения.Генератор псевдослучайных последовательностей признается качественным (т.е. вырабатывающем последовательности, соответствующие постатистическим свойствам истинно случайным), если для каждого тестаодновременно выполняются два условия:- относительное количество последовательностей, проходящихтест,принадлежит доверительному интервалу;- величина достигаемого уровня значимости, отражающего равномерность распределения р-значений, составляет не менее 0,0001.-142Результаты тестирования генератора псевдослучайных последовательностей, полученные при помощи программного комплекса Assess, отражаются в файле отчета, имеющем табличную форму.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
