$n$ là một biến thời gian chạy được chọn mỗi khi người dùng chạy triển khai.
Một cách tôi có thể nghĩ là sử dụng bất kỳ mật mã khối nào, chẳng hạn như AES, làm CSPRNG được gieo hạt để xáo trộn danh sách số một cách ngẫu nhiên $0, 1, \ldots, 2^n-1$. Bằng cách này, tôi đảm bảo không va chạm lên đến $2^n$ con số. Nhưng phương pháp này quá tốn kém vì nó sẽ yêu cầu tôi trao đổi $2^n$ con số.
Một cách khác tôi có thể nghĩ đến là sử dụng mật mã khối để tạo bản mã $c = \mathrm{enc}(\mathrm{0x000}\ldots, \mathrm{key})$, ở đâu $\mathrm{len}(c) \ge n$. Sau đó lấy số 1 $n$ nhiều bit của $c$; hãy gọi nó $c_n$. Sau đó làm: $c_n \oplus 0, c_n \oplus 1, \ldots, c_n \oplus 2^n-1$. Cách này hiệu quả, nhưng vấn đề là, tôi nghĩ, chuỗi không ngẫu nhiên. Ví dụ. $c_n \oplus 0$ nói chung là sẽ gần hơn với $c_n \oplus 1$ hơn, nói, $c_n \ocộng thêm 100$.
Câu hỏi: Có cách tiếp cận nào nhanh hơn không, trong đó tôi có thể sử dụng bất kỳ mật mã khối nào chỉ trong khoảng một lần, để tạo số tiếp theo, sao cho khi tôi lặp lại quy trình, tôi nhận được $2^n$ nhiều số duy nhất mà không có xung đột?
Theo một nghĩa nào đó, tôi đoán tôi có thể gọi nó là: một phiên bản trực tuyến của việc xáo trộn các con số $0, 1, \ldots, 2^n-1$, mà không cần duy trì danh sách trong bộ nhớ $2^n$ Dài.
Lý tưởng nhất là nếu tìm thấy xáo trộn trực tuyến hoàn hảo thì nó phải có phân phối này (trong đó $i$ là bất kỳ số nào trong $\{0, 1, \ldots, 2^n-1\}$ và $N_j$ là một biến ngẫu nhiên sẽ nhận giá trị của một số trong tập hợp đó trong $j^{th}$ cuộc gọi của trình xáo trộn trực tuyến lý tưởng):
$$\begin{split}
\Pr(N_0 = i) &= 1/2^n \
\Pr(N_1 = i) &= 1/(2^n - 1) \
\Pr(N_2 = i) &= 1/(2^n - 2) \
\vchấm & \
\Pr(N_{2^n-1} = i) &= 1/(2^n - (2^n-1)) = 1\
\end{split}$$
