Список генераторов случайных чисел 📖 Wikipedia

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

Как заметил Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений». Это выражение подчёркивает принципиальную невозможность получить «истинную» случайность с помощью конечного детерминированного алгоритма. Тем не менее ГПСЧ широко применяются в методах Монте-Карло, имитационном моделировании, криптографии и играх.

Алгоритмы в данном списке сгруппированы по типу лежащего в основе математического принципа.

Не существует универсального определения «хорошего» генератора случайных чисел: требования существенно различаются в зависимости от области применения. Для задач метода Монте-Карло важны длинный период и равномерность многомерного распределения, для криптографии — вычислительная непредсказуемость, для встроенных систем — скорость при минимальных ресурсах^[2].

Для статистического тестирования ГПСЧ применяются стандартизованные наборы тестов. Наиболее известные из них — Diehard (разработан Дж. Марсаглия в 1995 году) и TestU01 (П. Лекуер и Р. Симар, 2007), включающий тест BigCrush из более чем 100 статистических проверок^[3]. Провал даже одного теста из набора BigCrush считается серьёзным недостатком генератора.

Линейный конгруэнтный метод был предложен Д. Г. Лемером в 1949 году и опубликован в 1951 году^[4]. Генератор определяется рекуррентной формулой:

${\displaystyle X_{n+1}=(aX_{n}+c){\bmod {m}}}$

где ${\displaystyle m}$ — модуль, ${\displaystyle a}$ — множитель, ${\displaystyle c}$ — приращение, ${\displaystyle X_{0}}$ — начальное значение (зерно).

Недостатком метода является зависимость последующих членов последовательности: последовательность неизбежно зацикливается, а период не превышает ${\displaystyle m}$^[1].

Частный случай при ${\displaystyle c=0}$. Синоним: генератор Парка-Миллера^[5]. Используется в Cray RANF (${\displaystyle m=2^{48}}$, ${\displaystyle a=44\,485\,709\,377\,909}$) и компьютерах Sinclair ZX81 (${\displaystyle m=65537}$, ${\displaystyle a=75}$).

Регистр сдвига с линейной обратной связью (англ. Linear Feedback Shift Register, LFSR) генерирует биты, вычисляя исключающее ИЛИ нескольких позиций регистра и сдвигая результат. При правильно выбранных позициях обратной связи достигается максимальный период ${\displaystyle 2^{n}-1}$, где ${\displaystyle n}$ — разрядность регистра^[6].

LFSR-последовательности легко предсказываются с помощью алгоритма Берлекэмпа-Мэсси, поэтому не применяются в криптографии без дополнительной нелинейной обработки.

Вихрь Мерсенна (англ. Mersenne Twister, MT) — генератор, разработанный в 1997 году японскими учёными Макото Мацумото и Такудзи Нисимура^[7]. Основан на линейной рекуррентности над полем GF(2).

Ключевые характеристики:

• Период: ${\displaystyle 2^{19937}-1}$ (числа Мерсенна).
• Равномерность в 623 измерениях (против ≤ 5 у стандартных LCG).
• Скорость: в 2-3 раза быстрее стандартных LCG-генераторов.

Вихрь Мерсенна является одним из наиболее широко используемых ГПСЧ в научных вычислениях и включён в стандартные библиотеки Python, Ruby, R, PHP и других языков. Недостаток: последовательность поддаётся восстановлению по 624 последовательным значениям.

В 2003 году Джордж Марсаглия предложил семейство генераторов Xorshift, основанных исключительно на операциях исключающего ИЛИ и битовых сдвигов^[8]. Генераторы чрезвычайно быстры и компактны, однако базовая форма xorshift проходит не все тесты из набора BigCrush.

Более современные модификации, разработанные Дэвидом Блэкманом и Себастьяно Виньей. xoroshiro128+ (2016) и xoshiro256** (2018) сочетают операции XOR, сдвига и ротации с нелинейной выходной функцией. Используются в Rust, Julia и ряде игровых движков.

PCG (англ. Permuted Congruential Generator) — семейство ГПСЧ, предложенное М. Э. О’Нил в 2014 году. Основано на LCG с применением нелинейной функции перестановки к выходу. PCG превосходит вихрь Мерсенна по скорости при меньшем внутреннем состоянии и проходит все тесты BigCrush.

Генератор Фибоначчи с запаздыванием (англ. Lagged Fibonacci Generator, LFG) использует рекуррентное соотношение:

${\displaystyle X_{n}=X_{n-j}\circ X_{n-k}{\pmod {m}},\quad j<k}$

где ${\displaystyle \circ }$ — арифметическая или битовая операция (сложение, XOR и др.)^[1]. Разновидности:

• Аддитивный LFG (ALFG) — использует сложение; входит в библиотеку SPRNG.
• Мультипликативный LFG (MLFG) — использует умножение.

WELL (англ. Well Equidistributed Long-period Linear) — семейство ГПСЧ, разработанное в 2006 году Ф. Панньтоном, П. Лекуером и М. Мацумото^[9]. Генераторы серии WELL512, WELL1024, WELL19937 обеспечивают лучшее по сравнению с MT равномерное распределение и быстрее выходят из состояний с низкой энтропией («плохих» начальных значений).

Комбинированные генераторы объединяют несколько независимых ГПСЧ для повышения качества последовательности. Примеры:

• MRG32k3a (Лекуер, 1999) — комбинированный MRG, входящий в состав библиотеки RngStream^[10].
• Вихман-Хилл — комбинация трёх LCG-генераторов; реализован в ранних версиях Microsoft Excel.

Данная группа генераторов разработана для задач криптографии, где требуется вычислительная неотличимость от истинной случайности:

Аппаратный генератор случайных чисел использует физические источники энтропии, которые принципиально непредсказуемы:

• Тепловой шум — флуктуации напряжения в резисторе.
• Дробовой шум — случайность движения носителей заряда.
• Радиоактивный распад — регистрация времён между распадами атомов.
• Квантовый вакуум — флуктуации электромагнитного поля.
• Физические процессы в ОС — Linux /dev/random, Windows CryptGenRandom.

Известные реализации в процессорах:

Суперкомпьютерные задачи моделирования методом Монте-Карло требуют генерации большого числа независимых потоков случайных чисел, по одному на каждый вычислительный процесс^[11]. Для этого применяются специальные стратегии параллелизации:

• Разбиение периода (sequence splitting) — каждый процесс получает непересекающийся отрезок единого длинного периода.
• Скачок вперёд (jump-ahead) — быстрый переход в состояние, отстоящее на ${\displaystyle 2^{k}}$ шагов.
• Независимые потоки (independent streams) — каждый процесс инициализируется разным зерном, обеспечивающим независимость потоков.

SPRNG (англ. Scalable Parallel Random Number Generators) — библиотека с открытым исходным кодом, разработанная для масштабных параллельных задач Монте-Карло на суперкомпьютерах^[11]. Включает пять генераторов:

1. Комбинированный MRG (Combined Multiple Recursive Generator).
2. 48-битный LCG.
3. 64-битный LCG.
4. Модифицированный аддитивный LFG.
5. Мультипликативный LFG.

dSFMT (англ. double precision SIMD-oriented Fast Mersenne Twister) — оптимизированная версия вихря Мерсенна для SIMD-параллелизма, разработанная Мацумото и коллегами. Используется в задачах физического моделирования на GPU и многопроцессорных системах.

• Метод Монте-Карло — численное интегрирование, молекулярная динамика, квантовая химия.
• Имитационное моделирование — дискретно-событийное моделирование, моделирование трафика.
• Криптография — генерация ключей, nonce, инициализирующих векторов.
• Игры и графика — процедурная генерация игровых миров, текстур, звука.
• Тестирование программного обеспечения — фаззинг, стресс-тестирование.
• Машинное обучение — инициализация весов, дропаут, аугментация данных.

• Генератор псевдослучайных чисел
• Аппаратный генератор случайных чисел
• Вихрь Мерсенна
• Линейный конгруэнтный метод
• Метод Монте-Карло
• Криптографически стойкий генератор псевдослучайных чисел
• SPRNG

• Кнут, Д. Искусство программирования. Том 2: Получисленные алгоритмы. — 3-е изд.. — Вильямс, 2007. — ISBN 978-5-8459-0081-4.
• Фергюсон, Н.; Шнайер, Б. Практическая криптография. — Диалектика, 2005. — 421 с. — ISBN 5-8459-0733-0.
• Matsumoto, M.; Nishimura, T. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. — 1998. — Т. 8, № 1. — С. 3–30. — doi:10.1145/272991.272995.
• Mascagni, M.; Srinivasan, A. Algorithm 806: SPRNG: A scalable library for pseudorandom number generation. — 2000. — Т. 26, № 3. — С. 436–461. — doi:10.1145/358407.358427.
• Panneton, F.; L'Ecuyer, P.; Matsumoto, M. Improved long-period generators based on linear recurrences modulo 2. — 2006. — Т. 32, № 1. — С. 1–16. — doi:10.1145/1132973.1132974.
• L'Ecuyer, P.; Simard, R. TestU01: A C Library for Empirical Testing of Random Number Generators. — 2007. — Т. 33, № 4. — doi:10.1145/1268776.1268777.

• PCG — A Better Random Number Generator — официальный сайт
• Mersenne Twister Home Page — официальный сайт авторов