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

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

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

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

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

Сноска:

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

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

Ответ 9

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

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

Ответ 10

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