Псевдослучайность

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

Фон

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

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

В некоторых случаях, когда важно, чтобы последовательность была явно непредсказуемой, использовались физические источники случайных чисел, такие как радиоактивный распад, атмосферный электромагнитный шум, полученный из радио, настроенного между станциями, или смешанное время нажатия клавиш . Затраты времени, необходимые для получения этих чисел, приводят к компромиссу: использовать некоторые из этих физических показаний в качестве затравки для генератора псевдослучайных чисел.

История

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

Первая попытка предоставить исследователям готовый запас случайных цифр была предпринята в 1927 году, когда издательство Кембриджского университета опубликовало таблицу из 41 600 цифр, разработанную БАК Типпеттом . В 1947 году корпорация RAND генерировала числа с помощью электронного моделирования колеса рулетки; результаты были в конечном итоге опубликованы в 1955 году как «Миллион случайных цифр со 100 000 нормальных отклонений» .

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

В теоретической информатике распределение . является псевдослучайным против класса противников, если ни один противник из этого класса не может отличить его от равномерного распределения со значительным преимуществом Это понятие псевдослучайности изучается в теории сложности вычислений и имеет приложения к криптографии .

Формально, пусть S и T — конечные множества и пусть F = { f : S → T } — класс функций. Распределение является D над S ε- псевдослучайным относительно F , если для каждого f в F статистическое расстояние между распределениями $f(X)$ и $f(Y)$, где $X$ выбирается из D и $Y$ выбирается из равномерного распределения на S , не превосходит ε.

В типичных приложениях класс F описывает модель вычислений с ограниченными ресурсами, и каждый заинтересован в разработке распределений D с определенными свойствами, которые являются псевдослучайными по отношению к F . Распределение D часто указывается как результат работы генератора псевдослучайных чисел .

См. также

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

Дальнейшее чтение

• Дональд Э. Кнут (1997) Искусство компьютерного программирования , Том 2: Получисловые алгоритмы (3-е издание) . Аддисон-Уэсли Профессионал, ISBN   0-201-89684-2
• Гольдрейх, Одед (2008). Вычислительная сложность: концептуальная перспектива . Издательство Кембриджского университета. ISBN  978-0-521-88473-0 . См., в частности, главу 8: Генераторы псевдослучайных чисел, стр. 284–348, и Приложение C.2: Псевдослучайность, стр. 490–493.
• Вадхан, СП (2012). «Псевдослучайность». Основы и тенденции теоретической информатики . 7 (1–3): 1–336. дои : 10.1561/0400000010 .

Внешние ссылки

• HotBits: настоящие случайные числа, генерируемые в результате радиоактивного распада.
• Использование и создание случайных чисел криптографического качества
• В RFC 4086 подробно обсуждается использование последовательностей псевдослучайных чисел в криптографии.