首页 文章

java.util.Random真的是随机的吗?我怎么能产生52! (阶乘)可能的序列?

提问于
浏览
199

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

从这里开始,我怀疑 java.util.Random 是否真的是随机的;它实际上能够生成所有52!可能性?

如果没有,我怎样才能可靠地生成一个更好的随机序列,可以生成所有52个!可能性?

8 回答

  • 4

    选择随机排列需要同时具有比问题所暗示的越来越少的随机性 . 让我解释 .

    The bad news: need more randomness.

    你的方法的根本缺陷是它试图使用64位熵(随机种子)在~2226种可能性之间进行选择 . 要在~2226种可能性之间进行选择,你必须找到一种方法来生成226位熵而不是64位 .

    有几种方法可以生成随机位:dedicated hardwareCPU instructionsOS interfacesonline services . 在你的问题中已经有一个隐含的假设,你可以以某种方式生成64位,所以只做你想做的事情,只做四次,并将多余的比特捐给慈善机构 . :)

    The good news: need less randomness.

    一旦你有226个随机位,其余的就可以确定性地完成,因此 java.util.Random 的属性可以变得无关紧要 . 这是怎么回事 .

    假设我们生成所有52个!排列(与我同在)并按字典顺序对它们进行排序 .

    要选择其中一个排列,我们需要的是 052!-1 之间的单个随机整数 . 那个整数是我们的226位熵 . 我们将它用作我们排序的排列列表的索引 . 如果随机索引是均匀分布的,那么不仅可以保证所有排列都可以选择,它们将被等量地选择(这比问题所提出的更有保证) .

    现在,您实际上不需要生成所有这些排列 . 鉴于其在我们的假设排序列表中随机选择的位置,您可以直接生成一个 . 这可以使用Lehmer[1] code在O(n2)时间内完成(另请参见numbering permutationsfactoriadic number system) . 这里的n是你的牌组的大小,即52 .

    这个StackOverflow answer中有一个C实现 . 那里有几个整数变量会在n = 52时溢出,但幸运的是在Java中你可以使用 java.math.BigInteger . 其余的计算几乎可以按原样转录:

    public static int[] shuffle(int n, BigInteger random_index) {
        int[] perm = new int[n];
        BigInteger[] fact = new BigInteger[n];
        fact[0] = BigInteger.ONE;
        for (int k = 1; k < n; ++k) {
            fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
        }
    
        // compute factorial code
        for (int k = 0; k < n; ++k) {
            BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
            perm[k] = divmod[0].intValue();
            random_index = divmod[1];
        }
    
        // readjust values to obtain the permutation
        // start from the end and check if preceding values are lower
        for (int k = n - 1; k > 0; --k) {
            for (int j = k - 1; j >= 0; --j) {
                if (perm[j] <= perm[k]) {
                    perm[k]++;
                }
            }
        }
    
        return perm;
    }
    
    public static void main (String[] args) {
        System.out.printf("%s\n", Arrays.toString(
            shuffle(52, new BigInteger(
                "7890123456789012345678901234567890123456789012345678901234567890"))));
    }
    

    [1]不要与Lehrer混淆 . :)

  • 3

    您的分析是正确的:使用任何特定种子播种伪随机数生成器必须在shuffle之后产生相同的序列,将您可以获得的排列数限制为264.通过调用 Collection.shuffle 两次,传递 Random 对象,该断言是easy to verify experimentally用相同的种子初始化,并观察两个随机shuffle是相同的 .

    因此,对此的解决方案是使用允许更大种子的随机数发生器 . Java提供了SecureRandom类,可以使用几乎无限大小的 byte[] 数组进行初始化 . 然后,您可以将 SecureRandom 的实例传递给 Collections.shuffle 以完成任务:

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

    通常,伪随机数发生器(PRNG)如果其状态长度小于226位,则不能从52项列表的所有排列中进行选择 .

    java.util.Random 实现了一个模数为248的算法;因此它的状态长度只有48位,比我提到的226位小得多 . 您将需要使用具有更大状态长度的另一个PRNG - 特别是具有52阶乘或更大阶段的PRNG .

    另见article on random number generators中的"Shuffling" .

    这种考虑与PRNG的性质无关;它同样适用于加密和非加密PRNG(当然,无论何时涉及信息安全,非加密PRNG都是不合适的) .


    尽管 java.security.SecureRandom 允许传入无限长度的种子,但 SecureRandom 实现可以使用基础PRNG(例如,"SHA1PRNG"或"DRBG") . 这取决于PRNG 's period (and to a lesser extent, state length) whether it'能够从52个因子排列中进行选择 . (注意I define "state length"为“PRNG在不缩短或压缩该种子的情况下初始化其状态所能采取的种子的最大大小”) .

  • 149

    让我先提前道歉,因为这有点难以理解......

    首先,你已经知道 java.util.Random 根本不是完全随机的 . 它以完全可预测的方式从种子生成序列 . 你是完全正确的,因为种子只有64位长,它只能生成2 ^ 64个不同的序列 . 如果你以某种方式生成64个真正的随机位并使用它们来选择种子,你就无法使用该种子在所有52个之间随机选择!可能的序列概率相等 .

    然而,这个事实并没有任何影响,只要你特别关注2 ^ 64序列就可以了 . 可以生成 .

    让我们说你有一个更好的PRNG使用1000位种子 . 想象一下,你有两种方法来初始化它 - 一种方法是使用整个种子初始化它,并且一种方法会在初始化之前将种子散列到64位 .

    如果您不知道哪个初始化程序是哪个,您是否可以编写任何类型的测试来区分它们?除非你(足够)幸运地最终用相同的64位两次初始化坏的,否则答案是否定的 . 如果没有对特定PRNG实现中的某些弱点的详细了解,则无法区分这两个初始化器 .

    或者,假设 Random 类具有2 ^ 64个序列的数组,这些序列在远处的某个时间完全和随机选择,并且种子只是该数组的索引 .

    因此, Random 仅对其种子使用64位的事实实际上不一定是统计上的问题,只要没有很大的机会你将使用相同的种子两次 .

    当然,出于加密目的,64位种子是不够的,因为让系统两次使用相同的种子在计算上是可行的 .

    编辑:

    我应该补充一点,即使以上所有都是正确的, java.util.Random 的实际实现也不是很棒 . 如果您正在编写纸牌游戏,可以使用 MessageDigest API生成 "MyGameName"+System.currentTimeMillis() 的SHA-256哈希值,并使用这些位来改组牌组 . 通过上述论点,只要您的用户不是真正的赌博,您就不必担心 currentTimeMillis 会返回多长时间 . 如果您的用户真的是赌博,那么使用没有种子的 SecureRandom .

  • 18

    我将对此采取一些不同的方法 . 你的假设是正确的 - 你的PRNG无法击中所有52个!可能性 .

    问题是:你的纸牌游戏的规模是多少?

    If you're making a simple klondike-style game? 然后你绝对不需要全部52个!可能性 . 相反,看看它是这样的:一个玩家将有18个不同的游戏 . 即使考虑到'Birthday Problem',他们也会遇到第一个重复游戏 .

    If you're making a monte-carlo simulation? 然后你可能没事 . 由于PRNG中的'P',你可能不得不处理工件问题,但是你需要查看独特可能性的几个方面 . )另一方面,如果你正在处理大的迭代计数,那么,是的,你的低种子空间可能是一个交易破坏者 .

    If you're making a multiplayer card game, particularly if there's money on the line? 然后你're going to need to do some googling on how the online poker sites handled the same problem you'再问一下 . 因为虽然低种子空间问题对于普通玩家来说并不明显,但是如果它被攻击,那么它是可以利用的,不仅仅是找到更好的PRNG - 你需要像加密问题那样认真对待它 .

  • 9

    简短的解决方案与dasblinkenlight基本相同:

    // Java 7
    SecureRandom random = new SecureRandom();
    // Java 8
    SecureRandom random = SecureRandom.getInstanceStrong();
    
    Collections.shuffle(deck, random);
    

    You don't need to worry about the internal state. Long explanation why:

    以这种方式创建 SecureRandom 实例时,它会访问特定于操作系统的真随机数生成器 . 这是访问值的熵池,其包含随机位(例如,对于纳秒定时器,纳秒精度基本上是随机的)或内部硬件数发生器 .

    此输入(!)可能仍包含虚假跟踪,这些输入将被加载到加密强哈希中,从而删除这些跟踪 . 这就是使用CSPRNG的原因,而不是自己创建这些数字! SecureRandom 有一个计数器,用于跟踪使用了多少位( getBytes()getLong() 等)和 refills the SecureRandom with entropy bits when necessary .

    简而言之:只需忘记异议并使用 SecureRandom 作为真正的随机数生成器 .

  • 10

    如果您将数字视为一个位(或字节)数组,那么您可以使用此Stack Overflow问题中建议的(安全)_692504解决方案,然后将数组映射到 new BigInteger(byte[]) .

  • 26

    一种非常简单的算法是将SHA-256应用于从0向上递增的整数序列 . (如果需要,可以附加一个盐到"get a different sequence" . )如果我们假设SHA-256的输出是"as good as"在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]
    

相关问题