随机迭代整数序列，1 到 n
Randomly iterate through sequence of integers, 1 to n
我有一个要遍历的整数范围。您可以假设序列以 1 开始并以 n 结束，其中 n > 1。但是，我不想按顺序迭代它们。目标是以随机方式遍历所有这些。此外，n 可能非常大，可能达到数万亿，因此我无法将范围存储在内存中。有办法吗？
我知道有一种方法可以对内存中已有的数组执行此操作。当您不能一次存储整个范围时，可以做类似的事情吗？
您可以使用 Format-Preserving Encryption 来加密计数器。
选择一个对称密码来加密最多N个数字。（你可以使用AES-FFX提出的方案）然后生成一个高熵的随机密钥开始加密数字0， 1, 2, ... 向上。由于加密确保 1:1 映射并且良好的加密看起来是随机的，因此您最终将仅使用 O(1) 存储得到一系列非重复随机数。
counter mode (CTR) is a well known technique to create a cryptographically secure pseudo-random number generator (CSPRNG). Section 10.2.1. of NIST SP 800-90A 中块密码的使用提供了额外的提示。
由于随机性的质量 does not show any statistical weaknesses.
，建议使用 AES 作为基础块密码进行随机模拟
这个想法一点也不新鲜，并且已经被 Craig McQueen:
在 Whosebug 上多次提出
- Generating non-repeating random numbers in Python
- Unique (non-repeating) random numbers in O(1)?
- Generating millions of non-repeating random numbers in Java
另外 crypto.stackexchange 有几个关于此的帖子：
我有一个要遍历的整数范围。您可以假设序列以 1 开始并以 n 结束，其中 n > 1。但是，我不想按顺序迭代它们。目标是以随机方式遍历所有这些。此外，n 可能非常大，可能达到数万亿，因此我无法将范围存储在内存中。有办法吗？
我知道有一种方法可以对内存中已有的数组执行此操作。当您不能一次存储整个范围时，可以做类似的事情吗？
您可以使用 Format-Preserving Encryption 来加密计数器。
选择一个对称密码来加密最多N个数字。（你可以使用AES-FFX提出的方案）然后生成一个高熵的随机密钥开始加密数字0， 1, 2, ... 向上。由于加密确保 1:1 映射并且良好的加密看起来是随机的，因此您最终将仅使用 O(1) 存储得到一系列非重复随机数。
counter mode (CTR) is a well known technique to create a cryptographically secure pseudo-random number generator (CSPRNG). Section 10.2.1. of NIST SP 800-90A 中块密码的使用提供了额外的提示。 由于随机性的质量 does not show any statistical weaknesses.
，建议使用 AES 作为基础块密码进行随机模拟这个想法一点也不新鲜，并且已经被 Craig McQueen:
在 Whosebug 上多次提出- Generating non-repeating random numbers in Python
- Unique (non-repeating) random numbers in O(1)?
- Generating millions of non-repeating random numbers in Java
另外 crypto.stackexchange 有几个关于此的帖子：