Генераторы случайных чисел

Генераторы  случайных чисел

Цель работы: ознакомиться с генераторами случайный чисел, реализовать генератор случайных чисел методом Макларена -Марсальи, в системе программирования, а также провести статистический анализ полученной числовой последовательности в пакете StatGraphics.

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

Генератор Макларена-Марсальи (MacLaren-Marsaglia) — генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был предложен в 1965 году американскими математиками Джорджом Марсалья , и Дональдом Маклареном. В своих работах Дональд Кнут называет генератор Макларена-Марсальи — генератор М.

Преимущества метода в том, что он позволяет ослабить зависимость между членами последовательности

 

Недостатки метода Макларена –Марсальи

По крайней мере, выявлено четыре недостатка в генераторе при использовании его для криптографических целей. Все четыре тесно связаны друг с другом. Первые три недостатка нашёл Чарльз Реттер.

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

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

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

Четвертый недостаток связан с реализацией  данного метода. Зачастую генератор осуществляют, используя массивы, хранящие 32-х битные числа. Из-за этого возникает эффект ограничения элементов в последовательности  , которые могут быть сохранены в  , что является причиной группирования отдельных элементов в  , которые чётко различимы.

Идея и алгоритм решения  задачи

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

Генератор состоит из четырёх  основных стадии:

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

Последние три стадии могут  повторяться необходимое число  раз.

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

Метод серединных квадратов гораздо хуже, чем данный метод, так как у последнего достаточная случайность последовательностей   и  , которые не могут вырождаться.

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

 

 Особенности компьютерной реализации

 

 

 

 

 

 

 

 

 

 

Результаты статистического анализа

Итоговые результаты

Проведя анализ исследуемой  случайной величины мы рассчитали математическое ожидание=4897,85

Среднеквадратическое отклонение=2807,41

Дисперсия=7,88154*10⁶

Объем выборки=1000

А также проверили гипотезу о равномерном законе распределения  случайной величины с помощью  критерия согласия х² Пирсона. Так как максимальный уровень значимости

P-Value

0,114457

меньше критического, то гипотеза не согласуется.

 

 

 

 

 

 

 

 

 

Список литературы

1. Дональд Э. Кнут. Искусство программирования -  The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6

2. http://www.ngpedia.ru/id133857p1.html

 

 

Список исполнителей

1)  Гончаров Дмитрий-нахождение  информации о генераторе базовой  случайной величины методом Макларена-Марсальи, реализация генератора случайных чисел в системе программирования С, получение 1000 генераций случайной величины

2) Лукашеня Ирина-нахождение  информации о генераторах случайных  чисел, статистический анализ  полученной числовой последовательности  в пакете StatGraphics

3) Великанова Владлена- нахождение информации о генераторах случайных чисел , оформление отчёта о проделанной работе

4) Левшунова Кристина-доклад о проделанной работе