Существуют ли генераторы случайных чисел без состояния?
Есть ли разница между генерацией нескольких чисел с использованием одного генератора случайных чисел (ГСЧ) и генерацией одного числа для каждого генератора и его отбрасыванием? Обе реализации генерируют числа, которые одинаково случайны? Есть ли для этого разница между обычными RNG и защищенными RNG?
У меня есть веб-приложение, которое должно генерировать список случайных чисел от имени клиентов. То есть числа должны казаться случайными с точки зрения каждого клиента. Означает ли это, что мне нужно сохранять отдельный случайный RNG на сеанс клиента? Или я могу использовать один RNG для всех сеансов? Или я могу создать и отказаться от ГСЧ по запросу?
ОБНОВЛЕНИЕ: Этот вопрос касается того, является ли подмножество случайной последовательности также случайным?
10 ответов
Генератор случайных чисел имеет состояние - это действительно необходимая функция. Следующее "случайное" число является функцией предыдущего числа и начального числа / состояния. Пуристы называют их генераторами псевдослучайных чисел. Числа пройдут статистические тесты на случайность, но на самом деле они не случайны.
Последовательность случайных значений конечна и повторяется.
Думайте о генераторе случайных чисел как о перемешивании набора чисел и затем раздаче их в случайном порядке. Семя используется для "перемешивания" чисел. После того, как начальное число установлено, последовательность чисел является фиксированной и очень трудно предсказать. Некоторые семена будут повторяться раньше, чем другие.
У большинства генераторов период достаточно велик, чтобы никто не заметил его повторения. 48-битный генератор случайных чисел произведет несколько сотен миллиардов случайных чисел, прежде чем он будет повторяться - с (AFAIK) любым 32-битным начальным значением.
Генератор будет генерировать случайные значения только тогда, когда вы дадите ему одно начальное число и дадите ему выбросить значения. Если вы измените начальные числа, числа, сгенерированные с новым значением начальных чисел, могут не выглядеть случайными по сравнению со значениями, сгенерированными предыдущим начальным числом - все ставки отключаются при изменении начальных чисел. Так что не надо.
Надежный подход состоит в том, чтобы иметь один генератор и "раздавать" номера вашим различным клиентам. Не связывайтесь с созданием и отказом от генераторов. Не связывайтесь со сменой семян.
Прежде всего, никогда не пытайтесь написать свой собственный генератор случайных чисел. Встроенные генераторы в большинстве языковых библиотек действительно хороши. Особенно современные, которые используют более 32 бит.
Некоторые дистрибутивы Linux имеют /dev/random а также /dev/urandom устройство. Вы можете прочитать их один раз, чтобы заполнить генератор случайных чисел вашего приложения. Они имеют более или менее случайные значения, но они работают, собирая шум от случайных системных событий. Используйте их экономно, чтобы между использованиями было много случайных событий.
Я бы рекомендовал использовать один генератор несколько раз. Насколько я знаю, все генераторы имеют состояние. Когда вы заполняете генератор, вы устанавливаете его состояние на что-то, основанное на семени. Если вы продолжаете создавать новые, вполне вероятно, что семена, которые вы выберете, будут не такими случайными, как числа, сгенерированные с помощью одного генератора.
Это особенно верно для большинства генераторов, которые я использовал, которые используют текущее время в миллисекундах в качестве начального числа.
Аппаратные, истинные [1] генераторы случайных чисел возможны, но нетривиальны и часто имеют низкие средние показатели. Доступность также может быть проблемой [2]. Погугливание "дробного шума" или "радиоактивного затухания" в сочетании с "генератором случайных чисел" должно возвращать некоторые попадания.
Эти системы не должны поддерживать состояние. Вероятно, не то, что вы искали.
Как отмечалось другими, программные системы являются только псевдослучайными и должны поддерживать состояние.
Компромисс состоит в том, чтобы использовать аппаратный RNG для обеспечения энтропийного пула (сохраненного состояния), который сделан доступным для заполнения PRNG. Это делается явно в реализации linux для /dev/random [3] и /dev/urandom [4].
Это некоторый аргумент о том, насколько случайными являются входные данные по умолчанию для пула энтропии / dev / random.
Примечания:
- по модулю любые проблемы с нашим пониманием физики
- потому что вы ждете случайного процесса
- / dev / random обеспечивает прямой доступ к пулу энтропии, посеянному из различных источников, которые считаются действительно или почти случайными, и блокирует, когда энтропия исчерпана
- / dev / urandom похож на / dev / random, но когда энтопия исчерпана, используется криптографический хеш, который делает пул энтропии эффективно PRNG с состоянием
Если вы создаете ГСЧ и генерируете одно случайное число из него, а затем отбрасываете ГСЧ, то сгенерированное число является настолько же случайным, как начальное число, используемое для запуска ГСЧ.
Было бы гораздо лучше создать одну ГСЧ и извлечь из нее много чисел.
Обычно для посева нового состояния требуется немало времени, и создание новых каждый раз не очень помогает. Единственный случай, когда я могу подумать о том, что вам может понадобиться более одного PRNG, относится к разным системам, например, в игре казино у вас есть один генератор для перетасовки карт и отдельный генератор для генерирования комментариев, сделанных управляющими персонажами компьютера, таким образом ДЕЙСТВИТЕЛЬНО выделенный пользователи не могут угадать результаты, основанные на поведении персонажей.
Хорошим решением для посева является использование этого (Random.org), они бесплатно предоставляют случайные числа, сгенерированные из атмосферного шума. Это может быть лучшим источником для посева, чем использование времени.
Изменить: В вашем случае, я бы определенно использовал один PRNG на клиента, если бы не по какой-либо другой причине, кроме как для хороших стандартов программирования. В любом случае, если вы поделитесь одним PRNG среди клиентов, вы все равно будете предоставлять псевдослучайные значения каждому из них с качеством, равным качеству вашего PRNG. Так что это жизнеспособный вариант, но кажется плохой политикой для программирования
Как уже говорили люди, гораздо лучше один раз посеять PRNG и использовать его повторно. Безопасный PRNG - это просто тот, который подходит для криптографических приложений. Единственный способ повторного посева каждый раз дает разумно случайные результаты, это когда он исходит из действительно случайного "реального мира" источника - то есть специализированного оборудования. Даже тогда, возможно, что источник смещен, и теоретически будет лучше использовать тот же PRNG.
Стоит отметить, что Haskell - это язык, который пытается полностью устранить изменяемое состояние. Чтобы согласовать эту цель с жесткими требованиями, такими как IO (что требует некоторой формы изменчивости), необходимо использовать монады для передачи состояния из одного вычисления в другое. Таким образом, Haskell реализует свой генератор псевдослучайных чисел. Строго говоря, генерация случайных чисел является неотъемлемой операцией с состоянием, но Haskell может скрыть этот факт, переместив "мутацию" состояния в привязку (>>=) операция.
Это, вероятно, звучит немного абстрактно, и на самом деле не дает полного ответа на ваш вопрос, но я думаю, что оно все еще применимо. С теоретической точки зрения невозможно работать с ГСЧ без участия государства. Несмотря на это, существуют методы, которые можно использовать для смягчения этого взаимодействия и придания ему видимости, как будто вся операция не имеет состояния.
Как правило, лучше создать один PRNG и извлечь из него несколько значений. Создание нескольких экземпляров означает, что вы должны гарантировать, что начальные числа для экземпляров гарантированно уникальны, что потребует включения информации, специфичной для экземпляра.
Кроме того, существуют более "истинные" генераторы случайных чисел, но они обычно требуют специального оборудования, которое позволяет получать случайные данные из дисперсии электрического сигнала внутри компьютера. Если вы действительно не беспокоитесь об этом, я бы сказал, что генераторы псевдослучайных чисел, встроенные в языковые библиотеки и / или ОС, вероятно, достаточны, если ваше начальное значение не легко предсказать.
Использование защищенного PRNG зависит от вашего приложения. Для чего используются случайные числа? Если они представляют собой что-то реальное (например, что-то связанное с криптографией), вы не захотите использовать что-то меньшее.
Безопасные PRNG намного медленнее, и для них может потребоваться, чтобы библиотеки выполняли операции произвольной точности, проверяли первичность и т. Д. И т. Д.
Ну, пока они высеваются по-разному каждый раз, когда они создаются, то нет, я не думаю, что будет какая-то разница; однако, если бы это зависело от чего-то вроде времени, то они, вероятно, были бы неоднородными из-за предвзятого семени.