0

我想了解有关伪随机数生成的说明。我的问题是：

  • 在伪随机数生成中是否有机会获得重复数字？

  • 当我用谷歌搜索时，我发现了真正的随机数生成。我可以得到一些真正的随机数生成算法，以便我可以使用它

    SecureRandom.getInstance(字符串算法)

请以安全为优先进行指导。

4

4 回答 4

4

1）是的，您通常可以在 PRNG 中有重复的数字。实际上，如果你应用鸽子洞原理，证明非常简单（即，假设你在 32 位无符号整数集合上有一个 PRNG；如果你生成超过 2^32 个伪随机数，你肯定会有至少一个数字产生至少 2 次；在实践中，这会发生得更快；通常 PRNG 的算法将循环通过一个序列，并且您有一种方法来计算或估计该循环的大小，在该循环结束时，每个单个数字将开始重复，并且算法的图像通常比您从中获取数字的集合要小得多）。

如果您需要不重复的数字（因为安全性似乎是您关心的问题，请注意，这比允许重复数字的（伪）随机数序列安全性低！！！），您可以执行以下操作：

class NonRepeatedPRNG {
  private final Random rnd = new Random();
  private final Set<Integer> set = new HashSet<>();
  public int nextInt() {
    for (;;) {
      final int r = rnd.nextInt();
      if (set.add(r)) return r;
    }
  }
}

请注意，nextInt上面定义的方法可能永远不会返回！谨慎使用。

2）不，没有“真正的随机数生成算法”之类的东西，因为算法是已知的，你可以控制和预测（即，只需运行它，你就有输出；你确切地知道它的输出下次你用相同的初始条件运行它时），而真正的 RNG 根据定义是完全不可预测的。

对于最常见的非安全相关应用程序（即科学计算、游戏等），PRNG 就足够了。如果安全是一个问题（即，您想要加密的随机数），那么 CSPRNG（加密安全 PRNG）就足够了。

如果您的应用程序没有真正的随机性就无法工作，我真的很想知道更多关于它的信息。

于 2013-03-09T06:59:34.727 回答
3

是的，任何随机数生成器都可以重复。非重复随机数问题有三种通用解决方案：

  • 如果您想要一个大范围的数字，然后选择一个并拒绝它，如果它是重复的。如果范围很大，那么这不会导致太多的重复尝试。

  • 如果您想要一个小范围内的大量数字，则将所有数字放在一个数组中并打乱数组。Fisher-Yates算法是阵列改组的标准。从打乱的数组中按顺序取出随机数。

  • 如果您想要大范围的大量数字，请使用适当大小的加密算法。例如，对于 64 位数字，使用 DES 并按顺序加密 0、1、2、3、...。输出保证唯一，因为加密是可逆的。

于 2013-03-09T10:03:02.047 回答
0

伪 RNG 可以自我重复，但真正的 RNG 也可以自我重复——如果它们从不自我重复，它们就不是随机的。

一个好的 PRNG 一旦播种了一些（~128 位）真实熵，实际上与真正的 RNG 没有区别。与真正的 RNG 相比，您肯定不会得到明显更多的冲突或重复。

因此，您不太可能需要真正的随机数生成器，但如果您确实需要在random.org上查看 HTTP API 。他们的 API 由真正的随机源支持。随机性来自大气噪声。

于 2013-03-09T10:23:52.430 回答
0

如果 PRNG 或 RNG 从不重复数字，那将是……真的可以预测，实际上！想象一下数字 1 到 8 上的 PRNG。您会看到它打印出 2、5、7、3、8、4、6。如果 PRNG 尽最大努力不重复自己，现在您知道下一个数字将是1 - 这不再是随机的了！

所以 PRNGs 和 RNGs 默认情况下会产生带有重复的随机输出。如果你不想重复，你应该使用像 Fisher-Yates Shuffle ( http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle ) 这样的洗牌算法来随机洗牌你的数字数组想要，随机顺序。

此外，如果您需要用于加密目的的随机数生成源，请为您的语言寻找加密 PRNG 提供商。只要它在密码学上很强大就应该没问题 - 真正的 RNG 要贵得多（或需要延迟，例如使用 random.org），而且通常不需要。

于 2013-04-11T06:09:59.840 回答