6

你将如何生成一个非常非常大的随机数？我正在考虑 2^10^9（十亿位）的数量级。任何编程语言——我认为解决方案会翻译成其他语言。

我想要 [1,N] 上的均匀分布。

我最初的想法：

--您可以随机生成每个数字并连接。问题：即使是非常好的伪随机生成器也可能产生数百万位数的模式，对吧？

  • 您也许可以通过将随机数提高到随机指数来帮助创建大随机数。问题：您必须进行数学运算，以使结果数字仍然是随机的，并且您应该能够在合理的时间内（例如，一个小时）计算它。

  • 如果有帮助，您可以尝试在可能较小的范围内生成可能不均匀的分布（例如，使用实数）并进行变换。问题：这可能同样困难。

有任何想法吗？

4

5 回答 5

4

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

现在要生成随机位，您可以使用真正随机性的来源，这很昂贵。

或者您可能会使用一些加密安全的随机数生成器，例如带有随机密钥的 AES，用于加密后续位块的计数器。加密安全意味着不会有明显的模式。

于 2011-03-27T07:27:59.183 回答
2

这取决于您需要数据的目的。对于大多数目的，PRNG 快速而简单。但它们并不完美。例如，我记得听说过混沌系统的蒙特卡洛斯模拟非常擅长揭示 PRNG 中的潜在模式。

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

基础理论很简单。信息论告诉我们，没有冗余的信号和纯随机数据之间没有区别。因此，如果我们选择一个大文件（即大量信号），通过压缩去除冗余，并剥离标题，我们就会得到一个非常好的随机信号。加密在消除伪影方面做得非常好。然而，加密算法倾向于以块的形式进行。因此，如果有人能不顾一切地猜出文件开头发生了什么，那么该数据就更容易被猜到。但是随后反转文件并再次加密意味着他们需要知道整个文件和我们的加密，才能找到数据中的任何模式。

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

于 2011-03-27T16:04:51.360 回答
1

NTL：一个做数论的图书馆

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

RandomBnd、RandomBits、RandomLen——生成伪随机数的例程

ZZ RandomLen_ZZ(long l);
// ZZ = psuedo-random number with precisely l bits,
// or 0 of l <= 0.
于 2011-03-27T07:18:17.123 回答
0

即使是非常好的伪随机生成器也可能开发出数百万位数的模式，对吧？

来自关于伪随机数生成的维基百科：

PRNG 可以使用种子状态从任意起始状态开始。此后，当使用该状态初始化时，它将始终产生相同的序列。序列开始重复之前的最大长度由状态的大小决定，以比特为单位。但是，由于添加“状态”的每一位，最大周期的长度可能会加倍，因此很容易构建周期足够长的 PRNG，以用于许多实际应用。

您也许可以通过将随机数提高到随机指数来帮助创建大随机数

我假设您建议使用随机值填充科学计数法的值？

例如：1.58901231 x 10^5819203489

这样做的问题是您的分布将是对数的（或者是指数的？:) - 相同的差异，甚至不是）。您永远不会得到一个包含第百万位数字集的值，但在一个列中包含一个数字。

您可以尝试在可能较小的范围内生成可能不均匀的分布（例如，使用实数）并转换

不确定我是否理解这一点。听起来与指数解决方案相同，但问题相同。如果您正在谈论乘以常数，那么您将得到一个块状分布而不是对数（指数？）分布。

建议的解决方案

如果您只需要具有良好分布的非常大的伪随机值，请使用具有更大状态的 PRNG 算法。PRNG 的周期性通常是比特数的平方，因此即使是非常大的数字也不需要那么多比特。

从那里，您可以使用您的第一个解决方案：

您可以随机生成每个数字并连接

尽管我建议您使用 PRNG 返回的全部值（可能是 2^31 或 2^32），并用这些值填充字节数组，并根据需要将其拆分。否则你可能会丢掉很多随机性。此外，将您的值缩放到一个范围（或使用模数）很容易搞砸您的分布，因此尝试保持 PRNG 可以返回的最大位数还有另一个原因。但是，请小心将返回的位包含在您的字节数组中，否则您将再次在您的分发中引入块状。

但是，这些解决方案的问题是如何用足够随机的值填充（大于正常的）种子状态。您可能能够使用标准大小的种子（通过时间或 GUID 样式的人口填充），并使用来自较小 PRNG 的值填充您的大 PRNG 状态。如果您的数字分布的好坏不是关键任务，这可能会起作用。

如果您需要真正加密安全的随机值，唯一真正的方法是使用自然形式的随机性，例如http://www.random.org/中的随机值。自然随机性的缺点是可用性，而且许多自然随机设备需要一段时间才能生成新的熵，因此生成大量数据可能真的很慢。

您还可以使用混合种子并确保安全 - 仅使用自然随机种子（以避免生成缓慢），其余部分使用 PRNG。定期重新播种。

于 2011-03-27T07:33:05.453 回答
0

如果您有一个随机数生成器，可以生成 X 位的随机数。并且 [X1, X2, ... Xn ] 的级联位创建您想要的 N 位数字，只要每个 X 是随机的，我不明白为什么您的大数字对于所有意图都不会是随机的和目的。如果标准 C rand() 方法不够安全，我敢肯定还有很多其他库（如本线程中提到的那些）其伪随机数“更随机”。

于 2011-03-27T07:23:06.890 回答