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

Кажется случайным, но на самом деле порождается детерминированным, причинным процессом

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

Фон

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

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

В некоторых случаях, когда важно, чтобы последовательность была явно непредсказуемой, использовались физические источники случайных чисел, такие как радиоактивный распад, атмосферный электромагнитный шум, собираемый с радиоприемника, настроенного между станциями, или смешанные тайминги нажатий клавиш . ^{[1] [4]} Временные затраты, необходимые для получения этих чисел, приводят к компромиссу: использованию некоторых из этих физических показаний в качестве затравки для генератора псевдослучайных чисел.

История

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

Первая попытка предоставить исследователям готовый запас случайных цифр была предпринята в 1927 году, когда Cambridge University Press опубликовало таблицу из 41 600 цифр, разработанную LHC Tippett . В 1947 году корпорация RAND сгенерировала числа с помощью электронного моделирования колеса рулетки; ^[5] результаты были в конечном итоге опубликованы в 1955 году под названием A Million Random Digits with 100 000 Normal Deviates .

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

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

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

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

Смотрите также

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

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

• Дональд Э. Кнут (1997) Искусство программирования , том 2: Получисленные алгоритмы (3-е издание) . Addison-Wesley Professional, ISBN  0-201-89684-2
• Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0.См. особенно Главу 8: Псевдослучайные генераторы, стр. 284–348, и Приложение C.2: Псевдослучайность, стр. 490–493.
• Vadhan, SP (2012). «Псевдослучайность». Основы и тенденции в теоретической информатике . 7 (1–3): 1–336. doi :10.1561/0400000010.

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

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

Ссылки

1. Джордж Джонсон (12 июня 2001 г.). «Знатоки хаоса предлагают ценный продукт: случайность». The New York Times .
2. SP Vadhan (2012). Псевдослучайность . псевдослучайность, теория эффективного создания объектов, которые «выглядят случайными», несмотря на то, что они созданы с использованием небольшого количества случайности или без нее.
3. Марк Уорд (9 августа 2015 г.). «Исследователи предупреждают, что случайные числа в Интернете слишком слабы». BBC .
4. Джонатан Кнудсон (январь 1998 г.). «Javatalk: Подковы, ручные гранаты и случайные числа». Sun Server . стр. 16–17.
5. "Миллион случайных цифр". RAND Corporation. Январь 2001 г. Получено 30 марта 2017 г.
6. Одед Голдрайх. Вычислительная сложность: концептуальная перспектива. Cambridge University Press. 2008.
7. «Псевдослучайность» (PDF) .
8. D. Eastlake, 3rd; J. Schiller; S. Crocker (июнь 2005 г.). Требования случайности для безопасности. doi : 10.17487/RFC4086 . BCP 106. RFC 4086.{{citation}}: CS1 maint: числовые имена: список авторов ( ссылка ) Лучшая общепринятая практика. Отменяет RFC 1750.