Из Википедии, бесплатной энциклопедии
  (Перенаправлено из псевдослучайного )
Перейти к навигации Перейти к поиску

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

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

История [ править ]

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

Первая попытка предоставить исследователям готовый набор случайных цифр была предпринята в 1927 году, когда издательство Cambridge University Press опубликовало таблицу из 41600 цифр, разработанную LHC Tippett . В 1947 году RAND Corporation произвела числа путем электронного моделирования колеса рулетки; [4] результаты были в конечном итоге опубликованы в 1955 году как «Миллион случайных цифр со 100 000 нормальных отклонений» .

Непредсказуемость как «почти случайная» [ править ]

Использование радиоактивного вещества, извергающего электроны и гамма-лучи, распадающиеся случайным образом, или получение непредсказуемых последовательностей данных с использованием радио, настроенного между станциями, сбор атмосферного шума дает краткосрочную непредсказуемость. [1] Время, необходимое для получения этих чисел, привело к компромиссу: использование некоторых из этих физических значений в качестве «затравки» для получения большего количества. Чем меньше «случайных» чисел, не являющихся начальными, тем более случайными кажутся числа. Один из компромиссов - смешивать время между нажатиями клавиш людьми. [5]

Действия людей , как было доказано , чтобы быть полезным для воспроизводимости за многофакторной аутентификации , [6] и исследования броуновского движения показали , как статистика и вероятностные модели могут предсказать , что группа будет делать, даже если определенное движение является случайным. [7]

Предсказуемость числовых последовательностей псевдослучайных , полученных с помощью детерминированного алгоритма является, в коротких кластерах, казалось бы , случайным образом . [8]

По вычислительной сложности [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ a b Джордж Джонсон (12 июня 2001 г.). «Ценители хаоса предлагают ценный продукт: случайность» . Нью-Йорк Таймс .
  2. ^ «Врожденные недостатки Proof-of-Stake» .
  3. ^ Марк Уорд (9 августа 2015 г.). «Случайные числа Интернета слишком слабы, - предупреждают исследователи» . BBC .
  4. ^ a b «Миллион случайных цифр» . Корпорация РЭНД . Проверено 30 марта 2017 года .
  5. ↑ Джонатан Кнудсон (январь 1998 г.). «Javatalk: подковы, ручные гранаты и случайные числа». Вс сервера . С. 16–17.
  6. ^ Эз Видр (6 ноября 2007). «Научная фантастика? Биометрическая аутентификация ClassifEye для сотовых телефонов» .
  7. ^ 1880,статья Торвальда Н. Тиле с использованием метода наименьших квадратов (основа регрессионного анализа)
  8. ^ SP Vadhan (2012). Псевдослучайность . псевдослучайность, теория эффективной генерации объектов, которые «выглядят случайными», несмотря на то, что построены с использованием небольшой или нулевой случайности
  9. ↑ Одед Гольдрайх. Вычислительная сложность: концептуальная перспектива. Издательство Кембриджского университета. 2008 г.
  10. ^ «Псевдослучайность» (PDF) .

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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