Случайное число и псевдослучайность¶

Случайное число (от англ. random — «произвольный, случайный») — число, выбранное или сгенерированное таким образом, что каждый элемент из допустимого набора имеет равную вероятность появления. Понятие «рандом» (калька с англ. random) широко используется в информатике, математике, статистике и повседневной речи для обозначения процесса выбора без видимой закономерности.

¶Математическое понятие

В теории вероятностей случайная величина — это величина, значение которой определяется исходом случайного эксперимента. Набор всех возможных исходов образует пространство элементарных событий, а вероятность каждого исхода задаётся распределением. Наиболее известное распределение — равномерное, при котором каждое значение из промежутка [a, b] имеет одинаковую вероятность.

Случайные числа находят применение в методе Монте-Карло — классе вычислительных алгоритмов, основанных на многократном случайном переборе. Метод был разработан в 1940-х годах физиками-теоретиками Станиславом Уламом, Джоном фон Нейманом и Николасом Метрополисом в рамках лос-аламосских исследований по ядерным технологиям.

¶Псевдослучайные числа в вычислительной технике

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

Основные генераторы псевдослучайных чисел:

• LCG (ликонгруэнтный генератор) — один из старейших алгоритмов: Xₙ₊₁ = (a·Xₙ + c) mod m. Использовался в ранних версиях языка C и стандартной библиотеке Java.
• Mersenne Twister — алгоритм 1997 года, разработанный Макото Матсумото и Цуёси Нисимурой. Генерирует последовательность длиной 2¹⁹⁹³⁷ − 1. Де-факто стандарт в большинстве языков программирования (Python, PHP, Ruby, R).
• xorshift — семейство быстрых генераторов, предложенных Джорджем Марсалиа в 2003 году.
• PCG — более новые генераторы, сочетающие простоту линейных конгруэнций с улучшенной случайностью.

ПСЧ инициализируется seed («зерном») — начальным значением. Один и тот же seed всегда даёт одну и ту же последовательность, что позволяет воспроизводить «случайные» события в играх и симуляциях.

¶Настоящая случайность

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

• время нажатия клавиш и движения мыши;
• шум дискового ввода-вывода;
• прерывания от аппаратуры.

В Linux это /dev/random и /dev/urandom, в Windows — криптографический провайдер (CryptGenRandom, в современных версиях — BCryptGenRandom). Криптографические генераторы, такие как HMAC-DRBG, детерминированно расширяют небольшой объём аппаратной энтропии в длинные последовательности.

¶Применение

Случайные числа используются повсеместно:

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

¶Случайность в философии и естествознании

Понятие случайности выходит за рамки информатики. В классической физике Ньютона считалось, что при точном знании начальных условий будущее полностью предсказуемо (детерминизм Лапласа). Квантовая механика ввела объективную случайность: результат измерения квантовой системы принципиально непредсказуем. Квантовые генераторы случайных чисел (например, использующие деление фотона) дают истинно случайные последовательности, проверяемые на отсутствие закономерностей.

¶История

Понятие случайности сопровождает человечество с древности — жребий, кости, астрология. Математическое изучение началось с работ Блеза Паскаля и Пьера де Ферма в XVII веке, заложивших теорию вероятностей. В XX веке случайность стала инженерной задачей: от атомных проектов, где возникла потребность в больших объёмах случайных чисел, до современных криптографических систем.

¶Источники

• Кнут Д. «Искусство программирования», том 2: «Псевдослучайные числа»
• Фелленц В. «Введение в криптографию»
• Марсалиа Дж. «Xorshift RNGs», Journal of Statistical Software, 2003
• Матсумото М., Нисимура Т. «Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator», ACM TOMACS, 1998
• Николас Метрополис, Станислав Улам. «The Monte Carlo Method», Journal of the American Statistical Association, 1949