Существуют ли генераторы случайных чисел без состояния?
https://stackoverflow.com/questions/203382
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли разница между генерацией нескольких чисел с использованием одного генератора случайных чисел (RNG) и генерацией одного числа на генератор и его отбрасыванием?Генерируют ли обе реализации одинаково случайные числа?Есть ли разница между обычными ГСЧ и безопасными ГСЧ для этого?
У меня есть веб-приложение, которое должно генерировать список случайных чисел от имени клиентов.То есть цифры должны казаться случайными с точки зрения каждого клиента.Означает ли это, что мне нужно сохранять отдельный случайный ГСЧ для каждого сеанса клиента?Или я могу использовать один ГСЧ для всех сеансов?Или я могу создавать и отбрасывать ГСЧ для каждого запроса?
Обновить:Этот вопрос связан с Является ли подмножество случайной последовательности также случайным?
Решение
Генератор случайных чисел имеет состояние - на самом деле это необходимая функция.Следующее "случайное" число является функцией предыдущего числа и начального значения / состояния.Пуристы называют их генераторами псевдослучайных чисел.Числа пройдут статистические тесты на случайность, но на самом деле не являются случайными.
Последовательность случайных значений конечна и действительно повторяется.
Представьте себе генератор случайных чисел как перетасовку набора чисел, а затем раздачу их в случайном порядке.Начальное значение используется для "перетасовки" чисел.Как только начальное значение задано, последовательность чисел фиксирована, и ее очень трудно предсказать.Некоторые семена повторяются раньше, чем другие.
Большинство генераторов имеют достаточно длительный период, чтобы никто не заметил его повторения.48-битный генератор случайных чисел выдаст несколько сотен миллиардов случайных чисел, прежде чем он повторится - с (AFAIK) любым 32-битным начальным значением.
Генератор будет Только генерируйте случайные значения, когда вы даете ему одно начальное значение и позволяете ему выдавать значения.Если вы измените начальные значения, то числа, сгенерированные с новым начальным значением, могут показаться случайными по сравнению со значениями, сгенерированными предыдущим начальным значением - при изменении начальных значений все ставки отменяются.Так что не надо.
Разумный подход заключается в том, чтобы иметь один генератор и "раздавать" цифры вашим различным клиентам.Не связывайтесь с созданием и удалением генераторов.Не связывайтесь с заменой семян.
Прежде всего, никогда не пытайтесь написать свой собственный генератор случайных чисел.Встроенные генераторы в большинстве языковых библиотек действительно хороши.Особенно современные, которые используют более 32 бит.
Некоторые дистрибутивы Linux имеют /dev/random и /dev/urandom устройство.Вы можете прочитать их один раз, чтобы запустить генератор случайных чисел вашего приложения.Они имеют более или менее случайные значения, но работают за счет "сбора шума" от случайных системных событий.Используйте их экономно, чтобы между использованиями было много случайных событий.
Другие советы
Я бы рекомендовал использовать один генератор несколько раз.Насколько я знаю, все генераторы имеют определенное состояние.Когда вы запускаете генератор, вы устанавливаете его состояние на что-то на основе начального значения.Если вы продолжаете создавать новые, вполне вероятно, что выбранные вами семена будут не такими случайными, как числа, сгенерированные с помощью всего одного генератора.
Это особенно верно для большинства генераторов, которые я использовал, которые используют текущее время в миллисекундах в качестве начального значения.
Аппаратные генераторы случайных чисел, правда [1], возможны, но нетривиальны и часто имеют низкие средние значения.Доступность также может быть проблемой [2].Поиск в Google "шума выстрела" или "радиоактивного распада" в сочетании с "генератором случайных чисел" должен вернуть несколько совпадений.
Эти системы не нуждаются в поддержании в рабочем состоянии.Вероятно, это не то, что вы искали.
Как отмечали другие, программные системы являются только псевдослучайными, и должен поддерживайте состояние.
Компромисс заключается в использовании аппаратного ГСЧ для обеспечения пула энтропии (сохраненного состояния), который становится доступным для заполнения PRNG.Это делается довольно явно в linux-реализации /dev/random [3] и /dev/urandom [4].
Это некоторый аргумент о том, насколько случайными на самом деле являются входные данные по умолчанию для пула энтропии /dev / random.
Примечания:
- по модулю любых проблем с нашим пониманием физики
- потому что вы ждете случайного процесса
- /dev/random предоставляет прямой доступ к пулу энтропии, полученному из различных источников, которые считаются действительно или почти случайными, и блокируется, когда энтропия исчерпана
- /dev/urandom похож на /dev/ random, но когда энтопия исчерпана, используется криптографический хэш, который эффективно превращает пул энтропии в PRNG с сохранением состояния
Если вы создаете ГСЧ и генерируете из него одно случайное число, а затем отбрасываете ГСЧ, сгенерированное число будет таким же случайным, как и начальное значение, используемое для запуска ГСЧ.
Было бы гораздо лучше создать один ГСЧ и извлечь из него много чисел.
Как люди уже говорили, гораздо лучше создать PRNG один раз и использовать его повторно.Защищенный PRNG - это просто тот, который подходит для криптографических приложений.Единственный способ, которым повторное заполнение каждый раз будет давать достаточно случайные результаты, - это когда оно поступает из действительно случайного источника "реального мира", то есть специализированного оборудования.Даже в этом случае возможно, что источник предвзят, и теоретически все равно будет лучше использовать тот же PRNG заново.
Обычно заполнение нового состояния занимает довольно много времени для серьезного PRNG, и создание новых каждый раз не очень поможет.Единственный случай, который я могу придумать, когда вам может понадобиться более одного PRNG, - это для разных систем, скажем, в игре казино у вас есть один генератор для перетасовки карт и отдельный для генерации комментариев, выполняемых управляющими компьютером персонажами, таким образом, ДЕЙСТВИТЕЛЬНО преданные пользователи не могут угадать результаты на основе поведения персонажей.
Хорошим решением для посева семян является использование это (Random.org) , они бесплатно предоставляют случайные числа, сгенерированные на основе атмосферного шума.Это могло бы быть лучшим источником для посева, чем использование времени.
Редактировать:В вашем случае я бы определенно использовал один PRNG для каждого клиента, хотя бы по одной другой причине, кроме как из-за хороших стандартов программирования.В любом случае, если вы разделяете один PRNG среди клиентов, вы по-прежнему будете предоставлять каждому псевдослучайные значения качества, равного качеству вашего PRNG.Так что это жизнеспособный вариант, но кажется плохой политикой для программирования
Стоит упомянуть, что Haskell - это язык, который пытается полностью исключить изменяемое состояние.Чтобы согласовать эту цель с жесткими требованиями, такими как ввод-вывод (который требует некоторой формы изменчивости), монады должны использоваться для передачи состояния от одного вычисления к следующему.Таким образом, Haskell реализует свой генератор псевдослучайных чисел.Строго говоря, генерация случайных чисел по своей сути является операцией с сохранением состояния, но Haskell способен скрыть этот факт, переместив состояние "мутация" в привязку (>>=) операция.
Вероятно, это звучит немного абстрактно, и на самом деле это не дает полного ответа на ваш вопрос, но я думаю, что это все еще применимо.С теоретической точки зрения, невозможно работать с ГСЧ без привлечения государства.Несмотря на это, существуют методы, которые могут быть использованы для смягчения этого взаимодействия и сделать его появиться как будто вся операция носит апатридный характер.
Как правило, лучше создать один PRNG и извлечь из него несколько значений.Создание нескольких экземпляров означает, что вам необходимо убедиться в том, что исходные данные для экземпляров гарантированно уникальны, что потребует включения информации, относящейся к конкретному экземпляру.
Кроме того, существуют более совершенные "истинные" генераторы случайных чисел, но они обычно требуют специализированного оборудования, которое выполняет такие действия, как получение случайных данных из дисперсии электрического сигнала внутри компьютера.Если вы действительно не беспокоитесь об этом, я бы сказал, что генераторов псевдослучайных чисел, встроенных в языковые библиотеки и / или операционную систему, вероятно, достаточно, если ваше начальное значение нелегко предсказуемо.
Использование защищенного PRNG зависит от вашего приложения.Для чего используются случайные числа?Если они представляют собой что-то действительно ценное (напримервсе, что связано с криптографией), вы бы не захотели использовать что-то меньшее.
Защищенные PRNG работают намного медленнее и могут потребовать, чтобы библиотеки выполняли операции произвольной точности, тестировали простоту и т.д. И т.п...
Ну, пока они засеваются по-разному каждый раз, когда создаются, тогда нет, я не думаю, что будет какая-то разница;однако, если бы это зависело от чего-то вроде времени, то они, вероятно, были бы неоднородными из-за смещенного начального значения.
