История создания генератора случайных чисел

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

Случайные числа

Что такое случайные числа? Возьмем произвольную последовательность цифр. Случайна ли она? Зависит ли это от того, какие числа она содержит? Или может от того откуда эти числа появились?

Случайной называется последовательность, появление в которой событий равновероятно и независимо от предыстории. На самом деле чтобы понять, является ли последовательность случайной нужно провести немало опытов. Немало это сколько? А вот тут точного ответа нет. Все зависит от необходимой степени уверенности. Чтобы быть уверенным на 100% необходимо провести бесконечное число опытов. В реальной жизни это сделать непросто, поэтому проводится количество опытов, в сотни или тысячи раз превышающее число возможных исходов. Достаточно ли этого? Решать вам!

История создания генератора случайных чисел

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

Более интересным представителем старинных генераторов случайных чисел является игральный кубик. Древнейшие игральные кости возрастом около 5200 лет были найдены в Иране[1]. По своей сути он представляет собой генератор, способный генерировать последовательность от 1 до 6 с равной вероятностью (если у него не смещен центр тяжести). В 1890 году английский исследователь Фрэнсис Гальтон описал способ использования игровых костей для генерации случайных чисел в научных целях.

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

Для прикладных задач были необходимы большие массивы данных. В 1939 М. Ж. Кендалл и Б. Бабингтон-Смит построили первую машину, генерирующую случайные числа для построения таблицы, содержащей 100000 случайных чисел. А через 16 лет корпорацией RAND, с использованием специальных устройств, была построена таблица из миллиона случайных чисел. Несмотря на оживление табличного метода в 1996 Марсальей, построившего 650 Мбайт случайных чисел, круг применимости таких таблиц очень узок

Гораздо большее распространение получили генераторы случайных чисел, генерирующие их в реальном времени. В 1951 году в компьютер Ferranti Mark 1 была включена программа, идея которой принадлежала А. Тьюрингу, генерирующая случайные числа, используя шум Резистора. А в 1957 году была изобретена машина ERNIE (Electronic Random Number Indicator Equipment), четвертая версия которой была представлена в 2004 году. Это устройство изначально предназначено для генерации номеров выигрышных облигаций в британской лотерее[2].

Задача получения «случайной» последовательности чисел с помощью компьютера на удивление сложна. Интуитивно это можно обосновать тем фактом, что философия цифровых систем и архитектура современных ЭВМ направлены на достижение абсолютной точности, на уничтожение даже намёка на неопределённость в результате работы. Хранимые и передаваемые данные заверяются контрольными суммами, электрические цепи дублируются.

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

Казалось бы, природа предоставляет достаточно хаоса, почему бы не использовать его. Достаточно сделать оцифровывающее устройство для некоторого процесса (тепловые шумы, вспышки на солнце, кидание монетки), подключить его к компьютеру, и дело в шляпе.
Однако практическое применение «чистых» аппаратных ГСЧ ограничено следующими факторами:

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

Во-вторых, статистические характеристики такой последовательности могут быть не самые лучшие — распределение не то или меняется со временем, ширина чисел меньше требуемой, тенденция выдавать нули чаще, чем единицы (англ. bias) и т.п.

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

Наконец, энергопотребление и размеры ГСЧ могут быть неподходящими для мобильных устройств[3].