Введение

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

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

В курсовой работе будет объяснено, как работает линейный конгруэнтный метод (который чаще всего используется в функции random), метод получения случайных чисел с помощью полиномиального счётчика (который часто используется для тестирования аппаратуры) и алгоритм Блюма, Блюма и Шуба.

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

В равномерно распределённой последовательности нулей и единиц нули в среднем будут встречаться в 50% случаев. Но это вовсе не значит, что в последовательности из 1000 цифр будет ровно 500 нулей. Более того, в последовательности из 1000 цифр может быть 999 нулей, и вероятность того, что тысячный элемент будет равен нулю по-прежнему остаётся равной 0.5. На первый взгляд это кажется парадоксальным, но важно понимать, что все последовательности равновероятны. Если же мы будем рассматривать достаточно большую совокупность таких последовательностей, то в среднем в каждой из них будет 500 нулей.

Теперь перейдём к истории. В докомпьютерные времена случайные числа получали, вытаскивая разноцветные мячи из мешков, вытягивая карты, бросая кости. Понятно, что серьёзные исследования так проводить было нельзя, поэтому в 1927 года Типпетт опубликовал первую таблицу случайных чисел. Чуть позже люди попытались как-то автоматизировать этот процесс. Начали появляться машины, генерирующие случайные числа. Сейчас такие устройства тоже используются и называются источниками (генераторами) энтропии. Стоит заметить, что только такие устройства могут давать по-настоящему случайные числа. Но, к сожалению, генераторы энтропии довольно дороги, и не представляется возможным установить их в каждый ПК. Именно поэтому и возникла необходимость в алгоритмах получения случайных чисел.