Введение

Кажущиеся случайными, но на самом деле генерируемые детерминированным, причинно-следственным процессом. Псевдослучайная последовательность чисел – это последовательность, которая выглядит статистически случайной, хотя и была получена с помощью полностью детерминированного и воспроизводимого процесса. Проще говоря, проблема заключается в том, что многие источники случайности, доступные человеку (например, бросок игральной кости), основаны на физических процессах, которые нелегко реализовать в компьютерных программах.

Предыстория

Генерация случайных чисел находит широкое применение, например, для случайной выборки, методов Монте-Карло, настольных игр или азартных игр. Однако в физике большинство процессов, таких как гравитационное ускорение, являются детерминированными, то есть при одинаковых начальных условиях они всегда приводят к одному и тому же результату. К заметным исключениям относятся радиоактивный распад и квантовые измерения, которые в фундаментальной физике моделируются как истинно случайные процессы. Поскольку эти процессы не подходят для практического получения случайных чисел, используются псевдослучайные числа, которые в идеале должны обладать непредсказуемостью истинно случайной последовательности, несмотря на то, что они генерируются детерминированным способом. Во многих приложениях этот детерминированный способ представляет собой компьютерный алгоритм, называемый генератором псевдослучайных чисел, которому для начала работы необходимо предоставить число, называемое начальным зерном (seed). Поскольку одно и то же начальное зерно всегда будет давать одну и ту же последовательность, важно тщательно выбирать зерно и хранить его в секрете, особенно в приложениях, связанных с безопасностью, где непредсказуемость последовательности является критически важной характеристикой. В некоторых случаях, когда необходимо обеспечить демонстрационную непредсказуемость последовательности, используются физические источники случайных чисел, такие как радиоактивный распад, атмосферный электромагнитный шум, принимаемый радиоприемником, настроенным между станциями, или интервалы времени между нажатиями клавиш. Затраты времени на получение этих чисел приводят к компромиссу: использование некоторых из этих физических измерений в качестве начального зерна для генератора псевдослучайных чисел.

История

До появления современных компьютеров исследователям, которым требовались случайные числа, приходилось генерировать их различными способами (кости, карты, колеса рулетки). Результаты были в конечном итоге опубликованы в 1955 году как «Миллион случайных цифр со 100 000 нормальными отклонениями».

В вычислительной сложности

В теоретической информатике распределение считается псевдослучайным относительно класса противников, если ни один противник из этого класса не может отличить его от равномерного распределения с заметным преимуществом. Эта концепция псевдослучайности изучается в теории вычислительной сложности и находит применение в криптографии. Формально, пусть S и T – конечные множества, а F = {f: S → T} – класс функций. Распределение D над S является ε-псевдослучайным относительно F, если для любой функции f из F статистическое расстояние между распределениями D и U, где элементы распределения D выбираются из D, а элементы U – из равномерного распределения на S, не превышает ε. В типичных приложениях класс F описывает модель вычислений с ограниченными ресурсами, и целью является разработка распределений D с определенными свойствами, которые являются псевдослучайными относительно F. Распределение D часто задается как выход псевдослучайного генератора.