Случайные числа играют довольно важную роль для программистов разной направленности. Чаще всего случайные числа требуются в задачах моделирования, численного анализа, тестирования, криптографии и теории игр, но существует и множество других весьма специфических задач.
Но для начала давайте разберемся с понятием случайных чисел. Само понятие «случайное число» пришло из такого раздела математики, как теория вероятности, и всегда рассматривается в контексте какой-то последовательности, которая характеризуется тем, что каждое число последовательности не зависит от всех остальных чисел последовательности, то есть случайное число непредсказуемо, никогда нельзя с полной уверенностью предугадать, какое будет следующее число в случайной последовательности. Кроме того, случайные числа должны подчиняться равномерному распределению, то есть вероятность появления каждого числа равновероятна.
Теперь, когда у нас есть понимание, что такое случайные числа и для каких целей они необходимы, стоит вопрос получения какой-то случайной последовательности. Человек очень плох в качестве генератора случайных чисел. Это связано с нашим неверным интуитивным пониманием теории вероятностей. Компьютер справляется с задачей построения последовательности случайных чисел гораздо лучше.
Все генераторы случайных чисел делятся на два вида:
‒ True random number generator (ГНСЧ, генератор настоящих случайных чисел)
‒ Pseudo random number generator (ГПСЧ, генератор псевдослучайных чисел)
Эти два генератора задания случайной последовательности отличаются способом получения случайного числа.
ГНСЧ использует в качестве механизма получения случайного числа некий физический процесс, который сам по себе является непредсказуемым. Если оцифровать такой процесс (например, шумы атмосферы), то можно использовать его для генератора случайных чисел. ГПСЧ в свою очередь использует математические алгоритмы (полностью производимые компьютером) [2].
Рассмотрим сравнительную таблицу 1, которая показывает отличия между ГНСЧ и ГПСЧ.
Таблица 1
Отличия ГНСЧ иГПСЧ
|
ГНСЧ |
ГПСЧ |
|
|
1) Механизм |
Физический процесс |
Математика |
|
2) Равномерное распределение |
✔ |
✔ |
|
3) Независимость |
✔ |
✖ |
|
4) Скорость |
✖ |
✔ |
Стоить отметить, что, используя ГПСЧ, мы вычисляем наши числа по какой-то формуле, то естественно они будут как-то связаны между собой, поэтому псевдо-генераторы не обладают свойством независимости, они всегда связаны между собой, но этот недостаток компенсирует высокая скорость вычисления, так как какой-то физический процесс получает эти числа гораздо медленнее нежели чем, если мы будем вычислять их на процессоре.
Далее рассмотрим один из распространённых методов генерации псевдослучайных чисел — линейный конгруэнтный метод. В большинстве языков программирования именно этот метод используется в стандартной функции получения случайных чисел.
В линейном конгруэнтным методе случайное число вычисляется по следующей рекуррентной формуле: 
, где 
— модуль (
), 
— множитель (
), 
— приращение (
), 
— начальное значение, которое также иногда называют зерном (от англ. seed) (
).
Рассмотрим работу данного алгоритма при следующих значениях: 
, 
, 
, 
при 50 итерациях. Результаты вычислений представлены в виде графика на рис. 1.
Рис. 1. Пример работы алгоритма при , , ,
Как видно из графика, данный метод даёт нам повторяющиеся последовательности, но задача состоит в том, чтобы максимально удлинить уникальную часть последовательности (граница длины уникальной части определяется величиной ).
Теперь пусть 
(рис. 2).
Рис. 2. Пример работы алгоритма при , , ,
Как видно, последовательность сразу же начинает повторяться. Это происходит потому, что должно быть простым числом, чтобы периоды были гораздо больше. Вообще говоря, все коэффициенты формулы не должны быть случайными, чтобы полученная в результате последовательность была более случайной.
Теперь в качестве возьмём большое простое число, пусть 
(рис. 3).
Рис. 3. Пример работы алгоритма при , , ,
Как видно, если является большим простым числом, то случайная последовательность ведёт себя вполне непредсказуемо. При удачно подобранных коэффициентах данный метод может давать достаточно случайные числа.
Однако применять данный метод стоит в достаточно простых случаях, так как он не обладает криптографической стойкостью, так как зная четыре подряд идущих числа, криптоаналитик может составить систему уравнений, из которой можно найти , и .
Также существуют более случайные и надёжные модифицированные варианты данного метода генерации последовательностей псевдослучайных чисел. Кроме данного алгоритма применяется и ряд других алгоритмов, которые основаны на другой математике.
Литература:
- Генерация псевдослучайных чисел // habrahabr.ru. URL: https://habrahabr.ru/post/132217/ (дата обращения: 22.02.2017).
- Pseudorandom number generator // en.wikipedia.org. URL: https://en.wikipedia.org/wiki/Pseudorandom_number_generator (дата обращения: 22.02.2017).
- William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 2nd ed. — Cambridge University Press, 1992. — P. 277. — ISBN 0–521–43108–5.
