我一直在使用Random (java.util.Random)来洗牌一副52张牌。有52个!(8.0658175 e + 67)的可能性。然而,我发现java.util.Random的种子很长,它要小得多,为2^64 (1.8446744e+19)。

从这里开始,我怀疑java.util.Random是否真的那么随机;它真的能产生全部52个吗?可能性?

如果不是,我如何可靠地生成一个更好的随机序列,可以产生所有52!可能性?


当前回答

一般来说,伪随机数生成器(PRNG)如果最大周期长度小于226位,则不能从52项列表的所有排列中进行选择。

random实现了一个算法,其模量为248,最大周期长度不超过248,因此远小于2226(对应于我提到的226位)。您将需要使用另一个周期长度更大的PRNG,特别是最大周期长度为52 !或更大的PRNG。

请参见我关于随机数生成器的文章中的“洗牌”。

这一考虑与PRNG的性质无关;它同样适用于密码学和非密码学的prng(当然,非密码学的prng在涉及信息安全时是不合适的)。


虽然java.security.SecureRandom允许传入无限长度的种子,但SecureRandom实现可以使用底层的PRNG(例如,“SHA1PRNG”或“DRBG”)。这取决于PRNG的最大周期长度它是否能够从52个阶乘排列中进行选择。

其他回答

简单的解决方案,本质上是相同的dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

你不需要担心内部状态。解释原因:

当您以这种方式创建securerrandom实例时,它将访问特定于操作系统的实例 真正的随机数发生器。这是一个熵池,其中的值是 访问包含随机位(例如,对于纳秒计时器,纳秒 精度基本上是随机的)或内部硬件数字生成器。

此输入(!)可能仍然包含虚假的跟踪被送入 加密强哈希,删除这些跟踪。这就是使用这些csprng的原因,而不是为了自己创建这些数字!SecureRandom有一个计数器,用于跟踪使用了多少位(getBytes(), getLong()等),并在必要时用熵位重新填充SecureRandom。

简而言之:简单地忘记反对意见,使用securerrandom作为真正的随机数生成器。

我的实证研究成果是Java。随机并不完全是随机的。如果你尝试使用随机类" next高斯()方法,并生成足够大的样本总体的数字在-1和1之间,图是正态分布场称为高斯模型。

芬兰政府拥有的赌博书签每天都有一次,全年每天都抽彩票,中奖表显示书签书签以正常分布的方式给予奖金。我的Java模拟500万次抽奖显示,与nextInt() - method使用数字抽奖,奖金正态分布与My Bookmarker在每次抽奖中处理奖金相同。

我最好的选择是避免在结尾的每一个数字中出现3和7,这是事实,它们很少有获胜的结果。有几次通过避免在整数1-70之间的一列中的3和7个数字,赢得了5个选择中的5个。

芬兰彩票每周周六晚上抽一次,如果你在39个数字中抽12个,也许你会避开3和7个数字,在优惠券中获得5或6个正确的选择。

芬兰彩票有数字1-40可供选择,它需要4张优惠券来覆盖所有的数字与12号系统。总花费是240欧元,从长远来看,对于经常赌博的人来说,这太贵了,不玩就会破产。即使你把优惠券分享给其他可以购买的客户,如果你想盈利,你也必须非常幸运。

一个非常简单的算法是将SHA-256应用于从0开始递增的整数序列。(如果想要“获得不同的序列”,可以添加盐。)如果我们假设SHA-256的输出与0到2256 - 1之间的均匀分布整数“一样好”,那么我们就有足够的熵来完成任务。

为了从SHA256的输出中得到一个排列(当表示为整数时),只需要对其取模52、51、50…在这个伪代码中:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]

一般来说,伪随机数生成器(PRNG)如果最大周期长度小于226位,则不能从52项列表的所有排列中进行选择。

random实现了一个算法,其模量为248,最大周期长度不超过248,因此远小于2226(对应于我提到的226位)。您将需要使用另一个周期长度更大的PRNG,特别是最大周期长度为52 !或更大的PRNG。

请参见我关于随机数生成器的文章中的“洗牌”。

这一考虑与PRNG的性质无关;它同样适用于密码学和非密码学的prng(当然,非密码学的prng在涉及信息安全时是不合适的)。


虽然java.security.SecureRandom允许传入无限长度的种子,但SecureRandom实现可以使用底层的PRNG(例如,“SHA1PRNG”或“DRBG”)。这取决于PRNG的最大周期长度它是否能够从52个阶乘排列中进行选择。

您的分析是正确的:在伪随机数生成器中植入任何特定的种子都必须在洗牌后产生相同的序列,从而将您可以获得的排列数量限制为264。这个断言很容易通过调用Collection进行实验验证。shuffle两次,传递一个用相同种子初始化的随机对象,并观察两次随机shuffle是相同的。

因此,解决这个问题的方法是使用允许更大种子的随机数生成器。Java提供了securerrandom类,可以使用大小几乎无限制的byte[]数组进行初始化。然后,您可以将securerrandom的一个实例传递给集合。洗牌完成任务:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);