В статье приводится краткое описание процесса проектирования и разработки алгоритма, выдающего псевдослучайные числа.

Ключевые слова: псевдослучайные числа,алгоритм Лемера, алгоритм Вичмана-Хилла, линейный конгруэнтный метод, С++.

Введение

Генератор псевдослучайных чисел (ГПСЧ) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению.

ГПСЧ — одна из ключевых частей веб-безопасности. Она часто используется в криптографии, однако не все методы имеют хорошую криптозащищенность.

Методы генерации псевдослучайных чисел

Алгоритм для генерации псевдослучайных чисел существует большое множество. Рассмотрим некоторые из них:

1.1. Метод Фибоначчи с запаздываниями

Этот метод можно описать следующей формулой:

В данном алгоритме каждое последующее число является тем, которое было сгенерировано 7 шагов назад, плюс случайное число, которое было сгенерировано 10 шагов назад и деленное по модулю на большее значение .

1.2. Метод серединных квадратов

Данный метод был предложен Нейманом, суть данного метода заключается в том, что выбирается число меньше 1 разрядностью 2n и возводится в квадрат. Из полученного результата, разрядность которого должна быть 2*2n (если нет, то добавляются два нуля справа от полученного числа) выбираются 2 n чисел из середины полученного после возведения в квадрат числа. Число записывается после десятичной точки. Далее процедура повторяется.

1.3. Алгоритм Лемера.

Данный алгоритм был предложен Д.Лемером в 1988 году и в качестве входных значений берет a = 16807 и m = 2147483647, позднее в 1993 году Лемер использовал a = 48271 как более качественную альтернативу. Однако, алгоритм Лемера как и алгоритм Вичмана-Хилла является лишь частным случаем линейного конгруэнтного метода и рассчитывается по следующей формуле:

где m — модуль(m≥2), а — множитель (0≤a≤m)

1.4. Метод Вичмана-Хилла.

Этот алгоритм датируется 1982 годом. Идея Вичмана-Хилла заключается в генерации трех предварительных результатов и последующим их объединением в один финальный результат.

Так как данный алгоритм использует три разных генерирующих уравнения, ему требуется трое начальных значений, в данном случае это 30269, 30307, 30323 Алгоритм Вичмана-Хилла немногим сложнее, чем алгоритм Лемера, но его преимущество заключается в том, что он генерирует более длинную последовательность псевдослучайных чисел, прежде чем начнет повторяться.

1.5. Линейный Конгруэнтный Метод

Данный алгоритм — это один из методов генерации псевдослучайных чисел. Линейный конгруэнтный метод был предложен Д.Лемером в 1949 году. Суть данного метода заключается в вычислении последовательности случайных чисел по формуле:

где m — модуль(m≥2), а — множитель(0≤a≤m), с — приращение (0≤ <m). <="" p=""> </m).>

Эта последовательность называется линейной конгруэнтной последовательностью. Главным недостатком данного алгоритма является то, что он не криптографически стойкий.

Проектирование

Для реализации ГПСЧ был выбран язык C++, в качестве компилятора был выбран G++, так же для реализации математической части ГСПЧ использовались: алгоритм Вичмана-Хилла, алгоритм Лемера, которые в свою очередь основываются на линейном конгруэнтном алгоритме.

Для реализации методов ГПСЧ создадим три класса:

— Lemer — класс, в котором реализован метод Лемера;

— Witchman — класс, в котором реализован метод Вичмана-Хилла;

— MyClass — класс, в котором реализован мой метод, основанный на линейном конгруэнтном методе.

Алгоритм, написанный в классе MyClass, так же является частным случаем линейного конгруэнтного метода. В качестве входных значений используются константы b1, b2, b3. Получаемый результат генерируется путем генерации случайного seed’а алгоритмом Лемера и последующей генерации трех случайных чисел линейным конгруэнтным методом, результат же получается по следующей формуле:

, где

m1, m2 и m3 — произвольные целые числа типа int.

Для хранения данных полученных при генерации чисел воспользуемся массивом. Алгоритм работы программы представлен на рисунке 1.

Рис. 1

Результаты работы программы

В качестве выходных данных использованы те же массивы и переменные, что и во входных данных, только полностью обновленные, содержащие необходимые данные для вывода.

В результате запуска программы на монитор выводится окно, представленное на рисунке 2.

Рис. 2

Выводы

В результате был разработан генератор псевдослучайных чисел, основанный на алгоритме Вичмана-Хилла и алгоритме Лемера, которые в свою очередь основываются на линейном конгруэнтном алгоритме.

Литература:

1. Такач, Л. Комбинаторные методы в теории случайных процессов/ Л. Такач. — М.: 1999. — 266 c.
2. Столов, Евгений Генераторы случайных чисел. Математическая теория / Евгений Столов. — М.: LAP Lambert Academic Publishing, 2014. — 443 c.
3. Манин, Ю. И. Введение в теорию чисел / Ю. И. Манин, А. А. Панчишкин. — М: 1990. — 672 c.
4. Шор, Е. В мире случайностей / Е. Шор. — М.: [не указано], 1977. — 804 c.