Генератор псевдослучайных чисел из вычислимого нормального числа

Question

Легко ли можно построить PRNG таким образом? Почему это не сделано?

То есть, насколько я знаю, мы могли бы просто получить PRNG, который берет начальное число n. Когда вы запрашиваете случайный бит, он берет n-ую цифру двоичного расширения вычисляемого нормального числа и увеличивает n.

Сначала я подумал, что, возможно, мы не нашли вычислимое нормальное число, но мы

Это было полезно?

Представлять на рассмотрение

Решение

Это сделало бы прогнозирование вывода действительно простым.

Допустим, вы сгенерировали целое число 0x54a30b7f. Если у вас есть 4 ГБ пи (или случайный шум или фактическое нормальное число), есть вероятность, что будет только одно (или, может быть, несколько) вхождение этого конкретного целого числа, и я могу с достаточно высокой вероятностью предсказать все будущие числа. Это серьезная проблема в случае криптографически сильных PRNG. Если вместо простого последовательного сканирования вы используете какую-то функцию, мне просто нужно следовать этой функции, которая, если ее достаточно сложно проследить, превращается в PRNG сама по себе.

Если вас не волнует криптографическая сила вашего генератора, то есть гораздо более компактные способы генерации случайных чисел. Например, Mersenne Twister имеет гораздо больший период, не требуя справочной таблицы 4GiB.

Answer 1

Это сделало бы прогнозирование вывода действительно простым.

Допустим, вы сгенерировали целое число 0x54a30b7f. Если у вас есть 4 ГБ пи (или случайный шум или фактическое нормальное число), есть вероятность, что будет только одно (или, может быть, несколько) вхождение этого конкретного целого числа, и я могу с достаточно высокой вероятностью предсказать все будущие числа. Это серьезная проблема в случае криптографически сильных PRNG. Если вместо простого последовательного сканирования вы используете какую-то функцию, мне просто нужно следовать этой функции, которая, если ее достаточно сложно проследить, превращается в PRNG сама по себе.

Если вас не волнует криптографическая сила вашего генератора, то есть гораздо более компактные способы генерации случайных чисел. Например, Mersenne Twister имеет гораздо больший период, не требуя справочной таблицы 4GiB.