随机迭代整数序列，1到n [英] Randomly iterate through sequence of integers, 1 to n
问题描述
我想要迭代一系列整数。您可以假设序列以 1 开头，以 n 结尾，其中 n> 1 。但是，我不想按顺序遍历它们。目标是以随机的方式遍历所有这些。另外， n 可能非常大，可能在数万亿，所以我无法将范围存储在内存中。有没有办法做到这一点？
I have a range of integers I want to iterate through. You can assume the sequence begins with 1 and ends with n, where n > 1. However, I do not want to iterate through them sequentially. The goal is is iterate through all of them in a random fashion. In addition, n can be very large, in the trillions possibly, so I cannot store the range in memory. Is there a way to do this?
我知道有一种方法可以使用数组，已经在内存中。当你不能一次存储整个范围时可以做类似的事情吗？
I'm aware that there is a way to do this with an array, already in memory. Can something similar be done when you cannot store the entire range at once?
推荐答案
你可以使用格式保留加密以加密计数器。
You can use Format-Preserving Encryption to encrypt a counter.
选择一个对称密码，用于加密最多N的数字。（您可以使用 AES-FFX ）然后生成一个具有高熵的随机密钥，并开始加密数字0,1,2，......向上。由于加密确保了1：1的映射，并且良好的加密看起来是随机的，因此最终只使用O（1）存储的一系列非重复随机数。
Pick a symmetric cipher that is crafted to encrypt the numbers up to N. (You can use the proposed scheme of AES-FFX) Then generate a random key with high entropy and start to encrypt the numbers 0, 1, 2, ... upwards. Since the encryption ensures a 1:1 mapping and a good encryption looks random, you'll end up with a sequence of non-repeating random numbers using only O(1) storage.
在计数器模式（CTR）是一种众所周知的技术，用于创建加密安全伪随机数生成器（CSPRNG）。第10.2.1节。 NIST SP 800-90A 提供了其他提示。
由于随机性的质量，建议使用AES作为底层分组密码，因为随机性的质量没有显示任何统计上的弱点。
The usage of a block cipher in 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 gives additional tips. The usage of AES as the underlying block cipher is recommended for stochastic simulation since the quality of the randomness does not show any statistical weaknesses.
这个想法不过是新的，已经提出了通过 Craig McQueen 多次在stackoverflow上：
The idea is anything but new and was already proposed on stackoverflow multiple times by Craig McQueen:
- 在Python中生成非重复随机数
- < a href =https://stackoverflow.com/a/16097246/1743220> O（1）中的唯一（非重复）随机数？
- 用Java生成数百万个非重复随机数
- 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有几个关于此的线程：
Also crypto.stackexchange has several threads about this:
- Random Number Generator based on AES CTR
- How do I produce a stream of secure random numbers from AES-Counter mode?
这篇关于随机迭代整数序列，1到n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
