Существуют ли генераторы случайных чисел без состояния?

Question

Есть ли разница между генерацией нескольких чисел с использованием одного генератора случайных чисел (ГСЧ) и генерацией одного числа на генератор и его отбрасыванием? Обе реализации генерируют числа, которые одинаково случайны? Есть ли для этого разница между обычными RNG и защищенными RNG?

У меня есть веб-приложение, которое должно генерировать список случайных чисел от имени клиентов. То есть числа должны казаться случайными с точки зрения каждого клиента. Означает ли это, что мне нужно сохранять отдельный случайный RNG на сеанс клиента? Или я могу использовать один RNG для всех сеансов? Или я могу создавать и отбрасывать ГСЧ для каждого запроса?

ОБНОВЛЕНИЕ : Этот вопрос относится к Является ли подмножество случайной последовательности также случайным?

Answer 1

Генератор случайных чисел имеет состояние - это фактически необходимая функция. Следующее «случайное» число является функцией предыдущего числа и начального числа / состояния. Пуристы называют их генераторами псевдослучайных чисел. Числа пройдут статистические тесты на случайность, но на самом деле они не случайны.

Последовательность случайных значений конечна и повторяется.

Думайте о генераторе случайных чисел как о перемешивании набора чисел, а затем раздаче их в случайном порядке. Семя используется для "перемешивания" чисел. Как только начальное число задано, последовательность чисел является фиксированной и ее очень трудно предсказать. Некоторые семена будут повторяться раньше, чем другие.

У большинства генераторов период достаточно велик, чтобы никто не заметил его повторения. 48-битный генератор случайных чисел произведет несколько сотен миллиардов случайных чисел, прежде чем он повторится - с (AFAIK) любым 32-битным начальным значением.

Генератор будет только генерировать случайные значения, когда вы дадите ему одно начальное число и дадите ему выбросить значения. Если вы измените начальные числа, то числа, сгенерированные с новым начальным значением, могут не выглядеть случайными по сравнению со значениями, сгенерированными предыдущим начальным числом - все ставки отключаются при изменении начальных чисел. Так что не надо.

Разумный подход состоит в том, чтобы иметь один генератор и «раздавать» номера вашим различным клиентам. Не связывайтесь с созданием и отказом от генераторов. Не связывайтесь со сменой семян.

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

Некоторые дистрибутивы Linux имеют устройства /dev/random и /dev/urandom. Вы можете прочитать их один раз, чтобы заполнить генератор случайных чисел вашего приложения. Они имеют более или менее случайные значения, но они работают, собирая шум от случайных системных событий. Используйте их экономно, чтобы между использованиями было много случайных событий.

Answer 2

Я бы рекомендовал использовать один генератор несколько раз. Насколько я знаю, все генераторы имеют состояние. Когда вы заполняете генератор, вы устанавливаете его состояние на что-то, основанное на семени. Если вы продолжаете создавать новые, вполне вероятно, что семена, которые вы выберете, будут не такими случайными, как числа, сгенерированные с помощью одного генератора.

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

Answer 3

Аппаратные, истинные [1], генераторы случайных чисел возможны, но нетривиальны и часто имеют низкие средние показатели. Доступность также может быть проблемой [2]. Погугливание «дробного шума» или «радиоактивного затухания» в сочетании с «генератором случайных чисел» должно вернуть некоторые попадания.

Эти системы не должны поддерживать состояние. Вероятно, не то, что вы искали.

Как отмечалось другими, программные системы являются только псевдослучайными, и должен поддерживать состояние.

Компромиссом является использование аппаратного RNG для предоставления энтропийного пула (сохраненного состояния), который доступен для заполнения PRNG. Это делается явно в реализации linux для / dev / random [3] и / dev / urandom [4].

Это некоторый аргумент о том, насколько случайными являются входные данные по умолчанию для пула энтропии / dev / random.

---

Сноска:

1. по модулю любые проблемы с нашим пониманием физики
2. потому что вы ожидаете случайного процесса
3. / dev / random обеспечивает прямой доступ к пулу энтропии, посеянному из различных источников, которые считаются действительно или почти случайными, и блокирует, когда энтропия исчерпана
4. / dev / urandom похож на / dev / random, но когда энтопия исчерпана, используется криптографический хэш, который делает пул энтропии эффективно PRNG

Answer 4

Если вы создаете ГСЧ и генерируете из него одно случайное число, а затем отбрасываете ГСЧ, то сгенерированное число является таким же случайным, как начальное число, используемое для запуска ГСЧ.

Было бы намного лучше создать один ГСЧ и извлечь из него много чисел.

Answer 5

Обычно для посева нового состояния требуется серьезное PRNG, и создание новых каждый раз не очень помогает. Единственный случай, когда я могу подумать о том, где вам может потребоваться более одного PRNG, относится к разным системам, например, в игре казино у вас есть один генератор для перетасовки карт и отдельный генератор для генерирования комментариев, сделанных управляющими персонажами компьютера, таким образом ДЕЙСТВИТЕЛЬНО выделенный пользователи не могут угадать результаты, основанные на поведении персонажей.

Хорошим решением для посева является использование this (Random.org) , они бесплатно предоставляют случайные числа, сгенерированные из атмосферного шума. Это может быть лучшим источником для посева, чем использование времени.

Edit: В вашем случае, я бы определенно использовал один PRNG на клиента, если бы не по какой-либо другой причине, кроме как для хороших стандартов программирования. В любом случае, если вы разделяете один PRNG среди клиентов, вы все равно будете предоставлять каждому псевдослучайные значения качества, равного качеству вашего PRNG. Так что это приемлемый вариант, но кажется плохой политикой для программирования

Answer 6

Как уже говорили люди, гораздо лучше один раз посеять PRNG и использовать его повторно. Безопасный PRNG - это просто тот, который подходит для криптографических приложений. Единственный способ повторного посева каждый раз даст разумно случайные результаты, это когда он исходит из действительно случайного «реального мира» источника - то есть специализированного оборудования. Даже тогда, возможно, что источник смещен, и теоретически будет лучше использовать тот же PRNG.

Answer 7

Стоит отметить, что Haskell - это язык, который пытается полностью устранить изменяемое состояние. Чтобы согласовать эту цель с жесткими требованиями, такими как IO (что требует некоторой формы изменчивости), необходимо использовать монады для передачи состояния от одного вычисления к другому. Таким образом, Haskell реализует свой генератор псевдослучайных чисел. Строго говоря, генерация случайных чисел является неотъемлемой операцией с состоянием, но Haskell может скрыть этот факт, переместив «мутацию» состояния в операцию bind (>>=).

Возможно, это звучит немного абстрактно, и на самом деле это не дает полного ответа на ваш вопрос, но я думаю, что оно все еще применимо. С теоретической точки зрения невозможно работать с ГСЧ без участия государства. Несмотря на это, существуют методы, которые можно использовать, чтобы смягчить это взаимодействие и заставить его выглядеть так, как будто вся операция имеет состояние без состояния.

Answer 8

Использование защищенного PRNG зависит от вашего приложения. Для чего используются случайные числа? Если они представляют собой что-то реальное (например, что-нибудь криптографически связанное), вы не захотите использовать что-то меньшее.

Защищенные PRNG намного медленнее и могут потребовать от библиотек выполнения операций произвольной точности, тестирования на простоту и т. Д. И т. Д. *

Answer 9

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

Кроме того, существуют более «истинные» генераторы случайных чисел, но они обычно требуют специального оборудования, которое позволяет получать случайные данные из дисперсии электрического сигнала внутри компьютера. Если вы действительно не беспокоитесь об этом, я бы сказал, что генераторов псевдослучайных чисел, встроенных в языковые библиотеки и / или ОС, вероятно, достаточно, если ваше начальное значение не легко предсказать.

Answer 10

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