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

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

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

У физических источников случайных чисел существует ряд недостатков: Время и трудозатраты при установке и настройке по сравнению с программными ГПСЧ; Дороговизна; Генерация случайных чисел происходит медленнее, чем при программной реализации ГПСЧ; Невозможность воспроизведения ранее сгенерированной последовательности случайных чисел. В то же время случайные числа, получаемые из физического источника, могут использоваться в качестве порождающего элемента (англ. seed) для программных ГПСЧ. Такие комбинированные генераторы применяются в криптографии, лотереях, игровых автоматах.

Качественные требования, предъявляемые к ГПСЧ Достаточно длинный период, гарантирующий отсутствие зацикливания последовательности в пределах решаемой задачи. Длина периода должна быть математически доказана; Эффективность — быстрота работы алгоритма и малые затраты памяти; Воспроизводимость — возможность заново воспроизвести ранее сгенерированную последовательность чисел любое количество раз; Портируемость — одинаковое функционирование на различном оборудовании и операционных системах; Быстрота получения элемента последовательности чисел, при задании элемента, для любой величины; это позволяет разделять последовательность на несколько потоков (последовательностей чисел).

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

Например, для 4-значных чисел, начиная с 1234, получаем , где берём средние 4 цифры (дописав ноль в начале, если это необходимо). Затем возводим полученное число в квадрат , и так далее. Недостатком данного метода является ограниченность множества ПСЧ из-за того, что последовательность зацикливается — .

В 1951 году Д. Г. Лемер предложил линейный конгруэнтный метод, суть которого заключается в задании последовательности целых чисел рекурсивной формулой где  — целые и удовлетворяют следующим условиям: . Недостатком данного метода является зависимость от , так как , а также то, что ПСЧ зацикливается.

Детерминированные ГПСЧ

Алгоритм Большинство детерминированных ГПСЧ соответствуют структуре, предложенной П. Лекуером в 1994 году: , где  — это конечный набор состояний,  — вероятностное распределение в пространстве состояний , используемое для выбора начального состояния (англ. seed),  — функция перехода,  — пространство выходных значений, . Обычно , а состояние генератора задается рекуррентной формулой для . Выходное значение генератора ;  — последовательность псевдослучайных чисел. Так как конечно, то должны существовать некоторые конечные и такие, что . Значит, для всех будут выполняться условия и , потому что функции и детерминированные. Таким образом, последовательность — периодическая. Периодом ГПСЧ называется минимальное положительное .

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

Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937−1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.

Генератор псевдослучайных чисел включён в состав многих современных процессоров, например, RdRand входит в набор инструкций IA-32.

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

Список генераторов псевдослучайных чисел Ниже приведен список генераторов, которые исторически отметились в области изучения процесса генерации псевдослучайных чисел, либо благодаря своей исторической значимости, либо благодаря тому, что были инновационной моделью для своих эпох. Более того, несмотря на то, что это ГПСЧ, некоторые из них могут быть применимы в области криптографии. +АлгоритмАвторыСсылкиОписаниеMiddle-square / Метод середины квадратаДжон Фон Нейман1946ГПСЧ, который считается низкокачественным, но имеет большое историческое значение, поскольку является одним из первых алгоритмов. Lehmer генератор / Линейный конгруэнтный метод D. H. Lehmer1951Также известен как метод мультипликативных линейных конгруэнций и имеет большое влияние в этой области исследований. Он также известен как линейный конгруэнтный метод, основа которого со временем усовершенствовалась.Генератор Фибоначчи с запаздываниемG. J. Mitchell; D. P. Moore1958Очень влиятельный алгоритм в области изучения процессов генерации случайных чисел, вдохновивший других последующих великих авторов, таких как G. Marsaglia создатель теста на качество случайных чисел под названием "Diehard", например. Регистр сдвига с линейной обратной связью (LFSR) / Генератор TauswortheR. C. Tausworthe1965Генератор, конструкция которого повлияла на многие другие последующие ГПСЧ. Поэтому очень исторически важен. Также известен как генератор Таusworthe.A Limit Theorem for Conditioned Recurrent Random Walk Attracted to a Stable LawBarry Belkin, Vladimir V. Kurenkov, Daniel H. Wagner1970Ансамбль независимых частиц, движение которых описывается псевдослучайным блужданием, основанным на ГСПЧ в d-мерной решётке целых чисел.Wichmann & Hill генераторB. A. Wichmann; D. I. Hill1982Комбинация из трех небольших LCG, подходящих для 16-битных процессоров. Широко используется во многих программах, например, он использовался в Excel 2003 и некоторых более поздних версиях для функции RAND в Excel и был генератором по умолчанию в языке Python до версии 2.2. Rule 30 Вольфрам, Стивен1983Генератор на основе клеточных автоматов. Генератор Blum-Blum-Shub / Алгоритм Блюм — Блюма — ШубаБлюм, Мануэль; L. Blum; M. Shub1986Считается одним из самых безопасных генераторов с криптографической точки зрения, в основном благодаря внедрению в его формулу исследований и концепций, взятых из теории чисел.  За этот алгоритм Блюм, Мануэль был удостоен премии Алана Тьюринга 1995 года.Park-Miller генераторS. K. Park; K. W. Miller1988Конкретная реализация генератора Лемера, широко используемая, поскольку она включена в C++ в виде функции minstd_rand0, начиная с C++11. ACORNR. S. Wikramaratna1989Его название происходит от английского акронима ACORN, который расшифровывается как «Аддитивное конгруэнтное случайное число».MIXMAXG. K. Savvidy; N. G. Ter-Arutyunyan-Savvidy1991Это генератор, принадлежащий к классу матричных конгруэнтных линейных генераторов, обобщение метода линейных конгруэнций. Логика семейства генераторов MIXMAX основана на результатах эргодической теории и классической механики. Add-with-carry G. Marsaglia1991Модификация генераторов Фибоначчи с запаздыванием. Subtract-with-borrowG. Marsaglia; A. Zaman1991Алгоритм, полученный на основе генераторов Фибоначчи с запаздыванием. ISAACR. J. Jenkins Jr.1993Генератор криптографически защищенных криптографических данных (CSPRNG), разработанный Робертом Дж. Дженкинсом. Вихрь Мерсенна (Mersenne Twister, MTM. Matsumoto; T. Nishimura1996Это, вероятно, самый известный генератор в этом списке, в основном потому, что это алгоритм, реализованный в функции RAND языков программирования Python и R, в дополнение к его сильному присутствию в электронных играх, таких как Pro Evolution Soccer (PES). XorshiftG. Marsaglia2003Это очень быстрый подтип генераторов LFSR. Марсалья также предложил в качестве улучшения генератор xorwow, в котором выход генератора xorshift суммируется с последовательностью Вейля. Генератор xorwow является генератором по умолчанию в библиотеке CURAND интерфейса прикладного программирования nVidia CUDA для графических процессоров. Алгоритм FortunaШнайер, Брюс; Нильс Фергюсон2003<Алгоритм считается криптографически безопасным. CSPRNG, хорошо известный тем, что был внедрен в системы и продукты Apple. Well equidistributed long-period linear (WELL)F. Panneton; P. L'Ecuyer; M. Matsumoto2006Алгоритм, известный как дополнение к Mersenne Twister (MT), намеренно стремящийся скрыть его слабые стороны. Усовершенствованная система рандомизации (ARS) J. Salmon; M. Moraes; R. Dror; D. Shaw2011Упрощенная версия блочного шифра AES, обеспечивающая очень высокую производительность на системе, поддерживающей AES-NI. ThreefryJ. Salmon, M. Moraes, R. Dror and D. Shaw2011Упрощенная версия блочного шифра Threefish, подходящая для реализации на GPU. Philox (Филокс)J. Salmon, M. Moraes, R. Dror and D. Shaw2011Упрощение и модификация блочного шифра Threefish с добавлением S-box. Пермутированный конгруэнциальный генератор (PCG) M. E. O'Neill2014Модель, полученная с помощью линейного конгруэнтного метода.Генератор битов случайного цикла (RCB) R. Cookman2016RCB описывается как генератор битовых шаблонов, созданный для преодоления некоторых недостатков Вихрь Мерсенна (MT) и ограничения короткого периода/длины бита генераторов сдвигов/модулей. Middle Square Weyl Sequence RNG B. Widynski2017Разновидность оригинального метода средних квадратов Джона фон Неймана.Xoroshiro128+D. Blackman; S. Vigna 2018Модификация генератора Xorshift Г. Марсальи, одного из самых быстрых генераторов на современных 64-битных процессорах. Родственными генераторами являются xoroshiro128**, xoshiro256+ и xoshiro256***. 64-bit MELG (MELG-64)S. Harase; T. Kimoto2018Реализация 64-битных линейных генераторов F2 с первичным периодом Мерсенна.Squares RNGB. Widynski2020Основанная на счетчике версия Middle Square Weyl Sequence RNG. По конструкции похож на Philox, но работает значительно быстрее. Itamaracá (Ita)D. H. Pereira2021Известен как первый алгоритм PRNG, основанный на функции абсолютного значения. Itamaracá также является простой и быстрой моделью, которая генерирует апериодические последовательности случайных чисел.

Одноразовый блокнот