Регистрация Войти
Рейтинг:1
J. Linne avatar Crypto

«Бесконечная» (крпитографическая) псевдослучайная последовательность

флаг us
J. Linne

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

84
0 + 0
kelalaka avatar
флаг in
kelalaka
Для PRF $F$, $a_1 = F(1), a_2 = F(2||a_1), \ldots , a_i =F(i || a_i{-1})$, доказать невозможно, можно дать PRF, который терпит неудачу это.
0
Ответить
Рейтинг:2
avatar Crypto
флаг ph
bmm6o

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

Хотя это скорее теоретическая проблема, чем практическая. Даже простая CSPRNG имеет больше возможных состояний, чем она может посетить за всю жизнь Вселенной. Таким образом, вы можете использовать его «навсегда», прежде чем наблюдать такое повторение. Любое фактическое использование псевдослучайной последовательности обязательно конечно, и поэтому такие вопросы, как нормальность, применимые только к бесконечным последовательностям, на самом деле не имеют смысла. Вместо этого есть такие критерии, как «неотличимый от случайного», что кажется конечным аналогом того, о чем вы спрашиваете.

0 + 0
J. Linne avatar
флаг us
J. Linne
@poncho Я как бы думал об этом ... Возможно, какой-то PRNG, но использует другой модуль каждый раз, когда старый модуль «истекает» (т. Е. Последовательность вот-вот повторится).
0
Ответить
poncho avatar
флаг my
poncho
Обратите внимание, что если мы перейдем к более общей вычислительной модели, в которой мы позволяем размеру состояния расти во время генерации, мы действительно можем получить результат, который никогда не попадает в повторы (и величина необходимого роста является логарифмической в ​​сгенерированном выходе, т.е. , он растет довольно медленно). Конечно, как замечает bmm6o, нас обычно не волнует, повторяется ли последовательность после выхода $2^{1000}$ (или даже $2^{256}$), поэтому на практике это не встречается...
2
Ответить
флаг ph
bmm6o
Правильно, если бы вы реализовывали что-то подобное, вы, вероятно, следовали бы модели, описанной Пончо, где ваш алгоритм выделяет больше памяти по мере необходимости (поскольку ваши модули должны будут увеличиваться без ограничений). Дело в том, что когда вы выводите $n$ значений, вам нужно как минимум $log(n)$ битов состояния, чтобы избежать повторного посещения предыдущего состояния.
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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