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

219937−1, что более чем достаточно для многих практических приложений. Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Вихрь Мерсенна реализован в библиотеке gLib и стандартных библиотеках для PHP, Python и Руби. Алгоритм основан на следующем рекуррентном выражении: где n - целое, которое обозначает степень

рекуррентности, m - целое, 1< m < n, А - матрица размера WxW, с элементами из F2. В правой части  обозначает «старшие w-r бит» , и , «младшие r бит» Хк+1. 4 Тестирование псевдослучайных последовательностей   Псевдослучайные последовательности, порождаемые любым генератором для криптографических целей, подлежат обязательному тестированию. Тестирование псевдослучайных последовательностей — совокупность методов

определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т. п. Существует несколько методов тестирования ПСП: Ø     Графический тест Ø     Статистический   4.1 Графические тесты   К этой категории относятся тесты, результаты которых

отображаются в виде графиков, характеризующих свойства исследуемой последовательности. Среди них: 1.      гистограмма распределения элементов последовательности (позволяет оценить равномерность распределения символов в последовательности и определить частоту повторения каждого символа); 2.      распределение на плоскости (предназначено для определения зависимости между элементами

последовательности); 3.      проверка серий (позволяет определить равномерность отдельных символов в последовательности, а так же равномерность распределения серий из k бит); 4.      проверка на монотонность (служит для определения равномерности исходя из анализа невозрастающих и неубывающих подпоследовательностей); 5.      автокорреляционная функция (предназначена для оценки корреляции

между сдвинутыми копиями последовательностей и отдельных подпоследовательностей); 6.      профиль линейной сложности (тест оценивает зависимость линейной сложности последовательности от ее длины); 7.      графический спектральный тест (позволяет оценить равномерность распределения бит последовательности на основании анализа высоты выбросов преобразования Фурье). Результаты графических тестов