生成非常大的随机数

Question

你如何生成一个非常大的随机数？我想到的是2^10^9 (10亿位)。任何编程语言--我假设解决方案会被翻译成其他语言。

我想要1，N上的均匀分布。

我最初的想法是：

--你可以随机生成每一个数字并连接。问题:即使是非常好的伪随机生成器也有可能开发数百万位数字的模式，对吗？

• 你也许可以通过将随机数提高到随机指数来帮助创建大的随机数。问题:你必须使数学工作，以便得到的数字仍然是随机的，你应该能够计算它在合理的时间(例如，一个小时)。
• 如果有帮助，您可以尝试在可能较小的范围内生成可能不均匀的分布(例如使用实数)并进行转换。问题:这可能同样困难。

有什么想法吗？

Answer 1

生成log2(N)随机位以获得一个数字M，其中M可能是N的两倍大。重复，直到M在[1;N]范围内。

现在，要生成随机比特，可以使用真正的随机性源，这是非常昂贵的。

或者，您可以使用一些加密安全的随机数生成器，例如，带有随机密钥的AES对随后的比特块的计数器进行加密。加密安全意味着不可能有明显的模式。

Answer 2

这取决于你需要数据做什么。在大多数情况下，PRNG是快速和简单的。但它们并不完美。例如，我记得听说Monte对混沌系统的模拟很好地揭示了PRNG中潜在的模式。

如果这就是你正在做的事情，那么我在研究生院学到了一个简单的技巧来生成大量的随机数据。拿一个大的(最好是快速变化的)文件。(运行内核中的一些大数据结构是好的。)压缩它来增加熵。把头扔了。然后，为了好的措施，加密结果。如果您计划将其用于加密目的(而且您没有一个完美的熵数据集可供使用)，那么将其反转并再次加密。

根本的理论很简单。信息论告诉我们，没有冗余的信号和纯粹的随机数据没有区别。因此，如果我们选择一个大文件(即大量的信号)，消除冗余与压缩，并剥离头，我们有一个相当好的随机信号。加密在移除工件方面做得很好。然而，加密算法倾向于以块的形式向前推进。因此，如果有人，不管什么都可以，猜猜文件开头发生了什么，那么这些数据就更容易猜测了。但是，反转文件并再次加密意味着他们需要知道整个文件，以及我们的加密，才能在数据中找到任何模式。

选择一个快速变化的数据的原因是，如果您用完了数据并想要生成更多的数据，您可以再次回到同一个源。即使是小的变化，在这个过程之后，也会变成一个本质上不相关的随机数据集。

Answer 3

NTL:做数论的图书馆

这是我的编码理论和密码学老师推荐的。所以我想它做的很好，而且很容易使用。

RandomBnd，RandomBits，RandomLen -生成伪随机数的例程

ZZ RandomLen_ZZ(long l);
// ZZ = psuedo-random number with precisely l bits,
// or 0 of l <= 0.