$n$ — это переменная времени выполнения, выбираемая каждый раз, когда пользователь запускает реализацию.
Один из способов, который я могу придумать, - это использовать любой блочный шифр, скажем, AES, в качестве начального CSPRNG для случайного перемешивания списка чисел. $0, 1, \ldots, 2^n-1$. Таким образом, я гарантирую отсутствие столкновений до $2^n$ числа. Но этот подход слишком дорог, так как мне потребуется поменять местами $2^n$ числа.
Другой способ, который я могу придумать, - это использовать блочный шифр для генерации зашифрованного текста. $c = \mathrm{enc}(\mathrm{0x000}\ldots, \mathrm{key})$, куда $\mathrm{len}(c) \ge n$. Тогда возьмите 1-й $n$ много кусочков $с$; давайте назовем это $c_n$. Затем выполните: $c_n \oplus 0, c_n \oplus 1, \ldots, c_n \oplus 2^n-1$. Это эффективно, но проблема в том, что Я думаю, последовательность не случайна. Например. $c_n \oплюс 0$ обычно будет ближе к $c_n \oплюс 1$ чем, скажем, $c_n \oплюс 100$.
Вопрос: Есть ли более быстрый подход, при котором я могу использовать любой блочный шифр только один раз, чтобы сгенерировать следующее число, так что, когда я повторяю процесс, я получаю $2^n$ много уникальных номеров без коллизий?
В каком-то смысле я могу назвать это онлайн-версией перетасовки чисел. $0, 1, \ldots, 2^n-1$, без необходимости поддерживать список в памяти, который $2^n$ длинный.
В идеале, если найдена идеальная онлайн-тасовка, она должна иметь это распределение (где $я$ любое число в $\{0, 1, \ldots, 2^n-1\}$ и $N_j$ это случайная величина, которая будет принимать значение числа в этом наборе в $j^{th}$ вызов идеального онлайн тасовщика):
$$\начать{разделить}
\Pr(N_0 = i) &= 1/2^n \
\Pr(N_1 = i) &= 1/(2^n - 1) \
\Pr(N_2 = i) &= 1/(2^n - 2) \
\vdots & \
\Pr(N_{2^n-1} = i) &= 1/(2^n - (2^n-1)) = 1\
\end{split}$$
