O java.util.Random é realmente tão aleatório? Como posso gerar 52! possíveis seqüências (fatoriais)?

Eu tenho usado Random (java.util.Random)para embaralhar um baralho de 52 cartas. Existem 52! (8.0658175e + 67) possibilidades. No entanto, descobri que a semente para java.util.Randomé a long, que é muito menor em 2 ^ 64 (1.8446744e + 19).

A partir daqui, desconfio se isso java.util.Random é realmente aleatório ; é realmente capaz de gerar todos os 52! possibilidades?

Caso contrário, como posso gerar com segurança uma sequência aleatória melhor que possa produzir todos os 52! possibilidades?

A seleção de uma permutação aleatória requer simultaneamente mais e menos aleatoriedade do que a sua pergunta implica. Deixe-me explicar.

A má notícia: precisa de mais aleatoriedade.

A falha fundamental em sua abordagem é que ela está tentando escolher entre ~ ^2.226 possibilidades usando 64 bits de entropia (a semente aleatória). Para escolher razoavelmente entre ~ ²²⁶ possibilidades, você precisará encontrar uma maneira de gerar 226 bits de entropia em vez de 64.

Existem várias maneiras de gerar bits aleatórios: hardware dedicado , instruções de CPU , interfaces de SO , serviços online . Já existe uma suposição implícita na sua pergunta de que você pode, de alguma forma, gerar 64 bits, então faça o que quer que fosse fazer apenas quatro vezes e doe os bits em excesso para a caridade. :)

A boa notícia: precisa de menos aleatoriedade.

Depois de ter esses 226 bits aleatórios, o restante pode ser feito de forma determinística e, portanto, as propriedades de java.util.Randompodem ser irrelevantes . Aqui está como.

Digamos que geramos todos os 52! permutações (tenha paciência comigo) e classifique-as lexicograficamente.

Para escolher uma das permutações, basta um único número aleatório entre 0e 52!-1. Esse número inteiro é nossos 226 bits de entropia. Vamos usá-lo como um índice em nossa lista ordenada de permutações. Se o índice aleatório for distribuído uniformemente, você não apenas terá a garantia de que todas as permutações poderão ser escolhidas, mas também de forma equitativa (o que é uma garantia mais forte do que a pergunta).

Agora, você realmente não precisa gerar todas essas permutações. Você pode produzir uma diretamente, dada a sua posição escolhida aleatoriamente em nossa lista hipotética classificada. Isto pode ser feito em O (n ² ) usando o Lehmer ^[1] código (ver também numeração permutações e sistema número factoriadic ). O n aqui é o tamanho do seu baralho, ou seja, 52.

Há uma implementação C nesta resposta do StackOverflow . Existem várias variáveis ​​inteiras que estourariam para n = 52, mas felizmente em Java você pode usar java.math.BigInteger. O restante dos cálculos pode ser transcrito quase como está:

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] Não deve ser confundido com Lehrer . :)

Sua análise está correta: semear um gerador de números pseudo-aleatórios com qualquer semente específica deve produzir a mesma sequência após um shuffle, limitando o número de permutações que você pode obter para 2 ⁶⁴ . Essa afirmação é fácil de verificar experimentalmente chamando Collection.shuffleduas vezes, passando um Randomobjeto inicializado com a mesma semente e observando que os dois shuffles aleatórios são idênticos.

Uma solução para isso, então, é usar um gerador de números aleatórios que permita uma semente maior. Java fornece SecureRandomclasse que pode ser inicializada com byte[]matriz de tamanho praticamente ilimitado. Você pode passar uma instância de SecureRandompara Collections.shufflepara concluir a tarefa:

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

Em geral, um gerador de números pseudo-aleatórios (PRNG) não pode escolher entre todas as permutações de uma lista de 52 itens se o comprimento do estado for menor que 226 bits.

java.util.Randomimplementa um algoritmo com um módulo de 2 ⁴⁸ ; portanto, seu comprimento de estado é de apenas 48 bits, muito menos que os 226 bits a que me referi. Você precisará usar outro PRNG com um comprimento de estado maior - especificamente, um com um período de 52 fatorial ou superior.

Veja também "Baralhar" no meu artigo sobre geradores de números aleatórios .

Essa consideração é independente da natureza do PRNG; aplica-se igualmente a PRNGs criptográficos e não criptográficos (é claro que os PRNGs não criptográficos são inadequados sempre que a segurança da informação está envolvida).

Embora java.security.SecureRandompermita a transmissão de sementes de tamanho ilimitado, a SecureRandomimplementação pode usar um PRNG subjacente (por exemplo, "SHA1PRNG" ou "DRBG"). E depende do período desse PRNG (e, em menor medida, da duração do estado) se é capaz de escolher entre 52 permutações fatoriais. (Observe que eu defino "comprimento do estado" como o "tamanho máximo da semente que um PRNG pode ter para inicializar seu estado sem encurtar ou comprimir essa semente ").

Deixe-me pedir desculpas antecipadamente, porque isso é um pouco difícil de entender ...

Primeiro de tudo, você já sabe que java.util.Randomnão é completamente aleatório. Ele gera seqüências de maneira perfeitamente previsível a partir da semente. Você está completamente certo de que, como a semente tem apenas 64 bits, ela só pode gerar 2 ^ 64 sequências diferentes. Se você de alguma forma gerar 64 bits aleatórios reais e usá-los para selecionar uma semente, não poderá usá-la para escolher aleatoriamente entre todos os 52! seqüências possíveis com igual probabilidade.

No entanto, esse fato não tem importância , desde que você não gere mais do que 2 ^ 64 seqüências, desde que não haja nada de 'especial' ou 'visivelmente especial' nas sequências 2 ^ 64 que ele pode gerar .

Vamos dizer que você teve um PRNG muito melhor que usou sementes de 1000 bits. Imagine que você tinha duas maneiras de inicializá-lo - uma maneira inicializá-lo usando a semente inteira e uma maneira hash a semente até 64 bits antes de inicializá-la.

Se você não sabia qual inicializador era qual, poderia escrever algum tipo de teste para distingui-los? A menos que você tenha (des) tido a sorte de acabar inicializando o ruim com os mesmos 64 bits duas vezes, a resposta é não. Não foi possível distinguir entre os dois inicializadores sem um conhecimento detalhado de alguma fraqueza na implementação específica do PRNG.

Como alternativa, imagine que a Randomclasse tenha uma matriz de 2 ^ 64 sequências que foram selecionadas completamente e aleatoriamente em algum momento no passado distante, e que a semente seja apenas um índice dessa matriz.

Portanto, o fato de Randomusar apenas 64 bits para sua semente não é necessariamente um problema estatisticamente, desde que não haja chance significativa de que você use a mesma semente duas vezes.

Obviamente, para fins de criptografia , uma semente de 64 bits simplesmente não é suficiente, porque obter um sistema para usar a mesma semente duas vezes é computacionalmente viável.

EDITAR:

Devo acrescentar que, embora todas as opções acima estejam corretas, a implementação real de java.util.Randomnão seja impressionante. Se você estiver escrevendo um jogo de cartas, talvez use a MessageDigestAPI para gerar o hash SHA-256 "MyGameName"+System.currentTimeMillis()e use esses bits para embaralhar o baralho. Pelo argumento acima, desde que seus usuários não estejam realmente apostando, você não precisa se preocupar com o currentTimeMillisretorno por muito tempo. Se seus usuários estão realmente apostando, use SecureRandomsem sementes.

Vou adotar uma abordagem diferente. Você está certo em suas suposições - seu PRNG não será capaz de atingir todos os 52! possibilidades.

A questão é: qual é a escala do seu jogo de cartas?

Se você está fazendo um jogo simples no estilo klondike? Então você definitivamente não precisa de todos os 52! possibilidades. Em vez disso, veja o seguinte: um jogador terá 18 quintilhões de jogos distintos. Mesmo considerando o 'Problema do Aniversário', eles teriam que jogar bilhões de mãos antes de entrar no primeiro jogo duplicado.

Se você está fazendo uma simulação de monte-carlo? Então você provavelmente está bem. Você pode ter que lidar com artefatos devido ao 'P' no PRNG, mas provavelmente não terá problemas simplesmente devido a um baixo espaço de semente (novamente, você está vendo quintilhões de possibilidades únicas). Por outro lado, se você estiver trabalhando com uma grande contagem de iterações, sim, seu espaço inicial baixo pode ser um fator decisivo.

Se você está criando um jogo de cartas para vários jogadores, principalmente se houver dinheiro em jogo? Então você precisará pesquisar um pouco sobre como os sites de poker online lidaram com o mesmo problema que você está perguntando. Como o problema de pouco espaço inicial não é perceptível para o jogador comum, é explorável se vale a pena investir tempo. (Todos os sites de poker passaram por uma fase em que seus PRNGs foram 'hackeados', deixando alguém ver as cartas de todos os outros jogadores, simplesmente deduzindo a semente das cartas expostas.) Se esta é a situação em que você está, não 't simplesmente encontrar um melhor PRNG - você precisa tratá-lo tão a sério como um problema Crypto.

Solução curta, essencialmente igual à dasblinkenlight:

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

Collections.shuffle(deck, random);

Você não precisa se preocupar com o estado interno. Longa explicação do motivo:

Quando você cria uma SecureRandominstância dessa maneira, ela acessa um gerador de número aleatório verdadeiro específico do SO. Este é um pool de entropia onde são acessados ​​valores que contêm bits aleatórios (por exemplo, para um cronômetro de nanossegundos, a precisão de nanossegundos é essencialmente aleatória) ou um gerador interno de números de hardware.

Essa entrada (!) Que ainda pode conter traços falsos é inserida em um hash criptograficamente forte que remove esses traços. Essa é a razão pela qual esses CSPRNGs são usados, não para criar esses números! O SecureRandompossui um contador que rastreia quantos bits foram usados ​​( getBytes(), getLong()etc.) e enche os SecureRandombits de entropia quando necessário .

Resumindo: simplesmente esqueça as objeções e use-o SecureRandomcomo verdadeiro gerador de números aleatórios.

Se você considerar o número apenas como uma matriz de bits (ou bytes), talvez seja possível usar as Random.nextBytessoluções (seguras) sugeridas nesta questão de estouro de pilha e mapear a matriz para a new BigInteger(byte[]).

Um algoritmo muito simples é aplicar o SHA-256 a uma sequência de números inteiros incrementando de 0 para cima. (Um sal pode ser acrescentado, se desejado, para "obter uma sequência diferente".) Se assumirmos que a saída do SHA-256 é "tão boa quanto" números inteiros uniformemente distribuídos entre 0 e 2 ²⁵⁶ - 1, teremos entropia suficiente para o tarefa.

Para obter uma permutação da saída do SHA256 (quando expresso como um número inteiro), basta reduzir o módulo 52, 51, 50 ... como neste pseudocódigo:

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]