Теоретическая часть. 
Характеристика псевдослучайных чисел

Генерирование псевдослучайных чисел

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

В языке программирования C получить случайное число можно с помощью функции rand (), которая входит в стандартную библиотеку языка. Эта функция не принимает никакие параметры.

Для расстановки мин на игровом поле в игре «Сапер» необходимо случайным образом задать координаты клетки с миной. Для этого в программе используются различные методы генерирования таких координат.

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

Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло до криптографии. Генераторы псевдослучайных чисел широко используются в имитационном моделировании.

Термин ГПСЧ часто используется для описания ГПСБ (PRBG) — генераторов псевдослучайных бит, а так же различных поточных шифров. Предназначение ГПСЧ — генерация последовательностей чисел, которые невозможно отличить от случайных. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел.

Самые простые аппаратные ГСЧ (АГСЧ) основаны на тех свойствах элементов электронных схем, с которыми так долго и упорно боролись инженеры — схемотехники. Это свойство — собственные шумы электронного прибора.

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

Второму обширному классу АГСЧ лучше всего подойдет название «функциональный». Здесь в качестве «источника энтропии» используются фундаментальные функциональные свойства электронных приборов, например счетчиков Гейгера-Мюллера. Неприятной особенностью подобных устройств является необходимость применения радиоизотопных источников.

Третий класс АГСЧ — это «фундаментальный» класс. Наиболее яркий представитель «фундаментальных» АГСЧ — оптический квантовый генератор случайных чисел". Также существует устройство, в котором фундаментальные физические принципы, наносекундная синхронизация и самая современная электроника подчинены решению самой утилитарной задачи — получению случайных чисел, обновляющихся 100 тыс. раз в секунду.

Четвертый класс АГСЧ можно условно назвать «паразитным персонально-компьютерным». К их свойствам относятся прежде всего тепловые шумы и флуктуации в подсистеме аналогового ввода/вывода звукового адаптера.

В отдельный класс «курьезных» АГСЧ можно выделить специализированных роботов, методично бросающих… обычные игральные кости и оснащенных системой технического зрения для считывания выпавших очков [3].

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

• · Слишком короткий период/периоды
• · Последовательные значения не являются независимыми
• · Некоторые биты «менее случайны», чем другие
• · Неравномерное одномерное распределение
• · Обратимость

Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, алгоритм Блюма, Блюма и Шуба, Вихрь Мерсенна [5].

Линейный конгруэнтный метод Данный алгоритм был предложен Д. Х. Лемером в 1948 году. Применяется в простых случаях и не обладает криптографической стойкостью. Используется в качестве стандартного генератора многими компиляторами.

Этот алгоритм заключается в итеративном применении формулы (1):

(1).

где a > 0, c > 0, M > 0 — некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X₀ и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности X_j определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

• 1. НОД (c, m) = 1 (то есть c и m взаимно просты);
• 2. a — 1 кратно p для всех простых p — делителей m;
• 3. a — 1 кратно 4, если m кратно 4.

При реализации выгодно выбирать m = 2^e, где e — число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Формула (2) для вычисления n-й члена последовательности, зная только 0-й [7].

(2).

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

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

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

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле (3):

X (k) = (3).

где X (k) — вещественные числа из диапазона [0, 1),.

a, b — целые положительные числа, называемые лагами.

Для работы фибоначчиеву датчику требуется знать max (a, b) предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max (a, b) случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Рекомендуются следующие значения: a = 55, b = 24; a = 17, b = 5; a = 97, b = 33 [9].

Алгоритм Блюма, Блюма и Шуба (Blum Blum Shub, BBS).

Предложен в 1986 году Ленор и Мануэлем Блюм и Майклом Шубом.

BBS заключается в применении формулы (4):

x_n+1 = (x_n)² mod M (4).

где.

M=p*q.

является произведением двух больших простых p и q.

На каждом шаге алгоритма выходные данные получаются из x_n путём взятия либо бита чётности, либо одного или больше наименее значимых бит x_n.

Два простых числа, p и q, должны быть оба сравнимы с 3 по модулю 4 и НОД (ц (p-1), ц (q-1)) должен быть мал.

Интересной особенностью этого алгоритма является то, что для получения x_n необязательно вычислять все n — 1 предыдущих чисел, если известно начальное состояние генератора x₀ и числа p и q. n-ное значение может быть вычислено «напрямую» используя формулу (5):

x_n = x₀ ^{(2 ^ n) mod ((p-1)(q-1))} mod M (5).

Вихрь Мерсенна (Mersenne twister).

Разработан в 1997 японскими учёными Макото Мацумото и Такудзи Нисимура. Он обеспечивает быструю генерацию высококачественных псевдослучайных чисел, так как изначально был разработан с учётом ошибок, найденных в других алгоритмах.

Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна. Новейший и наиболее распространённый называется Mersenne Twister MT 19 937.

MT 19 937 имеет следующие ожидаемые свойства:

• 1. Он был разработан с целью иметь огромный период, размером 2^19 937? 1
• 2. Он имеет высокий порядок пространственного эквираспространения.
• 3. Он значительно быстрее, чем все остальные генераторы, за исключением статистически-дефектных генераторов.
• 4. Он статистически случаен во всех выходных битах [10].