Псевдослучайная последовательность чисел — это последовательность чисел , которая выглядит статистически случайной , несмотря на то, что она была получена в результате полностью детерминированного и повторяемого процесса. [1] Проще говоря, проблема в том, что многие источники случайности, доступные человеку (например, бросание игральных костей), основаны на физических процессах, которые недоступны компьютерным программам.
Генерация случайных чисел имеет множество применений, например, для случайной выборки , методов Монте-Карло , настольных игр или азартных игр . Однако в физике большинство процессов, таких как гравитационное ускорение, являются детерминированными, то есть они всегда приводят к одному и тому же результату из одной и той же отправной точки. Некоторыми заметными исключениями являются радиоактивный распад и квантовые измерения , которые моделируются как действительно случайные процессы в базовой физике. Поскольку эти процессы не являются практическими источниками случайных чисел, используются псевдослучайные числа, которые в идеале обладают непредсказуемостью действительно случайной последовательности, несмотря на то, что они генерируются детерминированным процессом. [2]
Во многих приложениях детерминированный процесс представляет собой компьютерный алгоритм , называемый генератором псевдослучайных чисел , которому сначала необходимо предоставить число, называемое случайным начальным числом . Поскольку одно и то же начальное число каждый раз будет давать одну и ту же последовательность, важно, чтобы начальное число было хорошо выбрано и хранилось в тайне, особенно в приложениях безопасности , где непредсказуемость шаблона является критически важной особенностью. [3]
В некоторых случаях, когда важно, чтобы последовательность была явно непредсказуемой, использовались физические источники случайных чисел, такие как радиоактивный распад, атмосферный электромагнитный шум, полученный из радио, настроенного между станциями, или смешанное время нажатия клавиш . [1] [4] Затраты времени, необходимые для получения этих чисел, приводят к компромиссу: использовать некоторые из этих физических показаний в качестве начального числа для генератора псевдослучайных чисел.
До появления современных вычислений исследователи, которым требовались случайные числа, либо генерировали их с помощью различных средств ( игральные кости , карты , колеса рулетки и т. д . ), либо использовали существующие таблицы случайных чисел.
Первая попытка предоставить исследователям готовый запас случайных цифр была предпринята в 1927 году, когда издательство Кембриджского университета опубликовало таблицу из 41 600 цифр, разработанную БАК Типпеттом . В 1947 году корпорация RAND произвела числа с помощью электронного моделирования колеса рулетки; [5] результаты были в конечном итоге опубликованы в 1955 году под названием « Миллион случайных цифр со 100 000 нормальных отклонений» .
В теоретической информатике распределение является псевдослучайным против класса противников, если ни один противник из этого класса не может отличить его от равномерного распределения со значительным преимуществом . [6] Это понятие псевдослучайности изучается в теории сложности вычислений и имеет приложения к криптографии .
Формально, пусть S и T — конечные множества и пусть F = { f : S → T } — класс функций. Распределение D по S является ε- псевдослучайным по отношению к F , если для каждого f в F статистическое расстояние между распределениями и , где отбирается из D и отбирается из равномерного распределения на S , не превосходит ε.
В типичных приложениях класс F описывает модель вычислений с ограниченными ресурсами, и каждый заинтересован в разработке распределений D с определенными свойствами, которые являются псевдослучайными по отношению к F . Распределение D часто указывается как результат работы генератора псевдослучайных чисел . [7]
псевдослучайность, теория эффективного создания объектов, которые «выглядят случайными», несмотря на то, что были построены с небольшим использованием случайности или вообще без нее.
{{citation}}: CS1 maint: числовые имена: список авторов ( ссылка ) Лучшая общая практика. Устаревший RFC 1750.