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

Question

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

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

UPDATE: Этот вопрос связан с Is a subset of a random sequence also random?

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

Было бы намного лучше создать единый RNG и нарисовать из него много чисел.

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

Answer 8

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

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

Answer 9

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

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

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

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

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

---

Сноски:

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

Answer 10

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

Безопасные PRNGs гораздо медленнее, и может потребовать библиотеки делать операцию произвольной точности и проверки простоты чисел, и т.д. и т.п. ...