$n$ este o variabilă de rulare aleasă de fiecare dată când utilizatorul rulează implementarea.
Un mod în care mă pot gândi este să folosesc orice cifru bloc, să zicem AES, ca un CSPRNG seminat pentru a amesteca aleatoriu lista de numere $0, 1, \ldots, 2^n-1$. În acest fel garantez lipsa de coliziune până la $2^n$ numere. Dar această abordare este prea costisitoare, deoarece va necesita să schimb $2^n$ numere.
Un alt mod la care mă gândesc este să folosesc cifrul bloc pentru a genera text cifrat $c = \mathrm{enc}(\mathrm{0x000}\ldots, \mathrm{key})$, Unde $\mathrm{len}(c) \ge n$. Apoi ia-l pe primul $n$ multe bucăți de $c$; hai să-i spunem $c_n$. Atunci fa: $c_n \oplus 0, c_n \oplus 1, \ldots, c_n \oplus 2^n-1$. Acest lucru este eficient, dar problema este că, cred, succesiunea nu este aleatorie. De exemplu. $c_n \oplus 0$ va fi în general mai aproape de $c_n \oplus 1$ decât, să zicem, $c_n \oplus 100$.
Intrebarea: Este vreo abordare mai rapidă, în care pot folosi orice cifru bloc pentru aproximativ o singură dată, pentru a genera următorul număr, astfel încât, pe măsură ce repet procesul, primesc $2^n$ multe numere unice fără ciocniri?
Într-un fel, cred că o pot numi: o versiune online a amestecării numerelor $0, 1, \ldots, 2^n-1$, fără a fi nevoie să menținem o listă în memorie, adică $2^n$ lung.
În mod ideal, dacă se găsește shuffle-ul online perfect, acesta trebuie să aibă această distribuție (unde $i$ este orice număr în $\{0, 1, \ldots, 2^n-1\}$ și $N_j$ este o variabilă aleatorie care va lua valoarea unui număr din acel set din $j^{th}$ apelul shuffler-ului ideal online):
$$\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) \
\vdots & \
\Pr(N_{2^n-1} = i) &= 1/(2^n - (2^n-1)) = 1\
\end{divizat}$$
