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

203

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?

Serj Ardovic
fonte
21
"como posso certamente gerar um número aleatório real acima de 52!" Os números de Randomnunca são números aleatórios reais . É um PRNG, onde P significa "pseudo". Para números aleatórios reais , você precisa de uma fonte de aleatoriedade (como random.org).
TJ Crowder
7
@ JimGarrison Não é isso que o OP está buscando. Ele está falando de 10 ^ 68 possíveis sequências. Como cada sequência pseudo-aleatória é identificada por sua semente, o OP diz que pode haver no máximo 2 ^ 64 seqüências diferentes.
precisa saber é o seguinte
6
Eu acho que é uma pergunta interessante e vale a pena pensar. Mas não posso deixar de me perguntar sobre o contexto do seu problema: o que exatamente está levando ao requisito de poder gerar todos os 52! permutações? Por exemplo, na ponte do mundo real, podemos embaralhar o baralho e distribuir uma carta de cada vez; no entanto, existem apenas ~ 6e11 mãos diferentes, pois muitas permutações diferentes resultam na mesma mão. Pensando na outra direção, você precisa de uma solução específica para 52 !, ou precisa de uma solução que generalize, digamos, dois baralhos embaralhados (104! / (2 ** 52) possibilidades ou ~ 2e150)?
NPE
9
@ NPE - Tome Solitaire (Klondike), por exemplo, 52! é exatamente o número de mãos possíveis ..
Serj Ardovic 9/18
3
Penso que esta é uma leitura interessante: superuser.com/a/712583
Dennis_E

Respostas:

153

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 ~ 226 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 2 ) 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 . :)

NPE
fonte
7
Heh, e eu tinha certeza de que o link no final seria New Math . :-)
TJ Crowder
5
@TJCrowder: Quase foi! Foram as variedades Riemannianas infinitamente diferenciáveis ​​que as balançaram. :-)
NPE
2
É bom ver pessoas apreciando os clássicos. :-)
TJ Crowder
3
Onde você obtém os 226 bits aleatórios em Java ? Desculpe, seu código não responde a isso.
Thorsten S.
5
Não entendo o que você quer dizer, o Java Random () também não fornece 64 bits de entropia. O OP implica uma fonte não especificada que pode produzir 64 bits para propagar o PRNG. Faz sentido supor que você possa solicitar a mesma fonte 226 bits.
Pare de prejudicar Monica
60

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 64 . 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);
dasblinkenlight
fonte
8
Certamente, uma semente grande não é garantia de que todos os 52! possibilidades seriam produzidas (sobre o que é especificamente essa pergunta)? Como um experimento mental, considere um PRNG patológico que pega uma semente arbitrariamente grande e gera uma série infinitamente longa de zeros. Parece bastante claro que o PRNG precisa satisfazer mais requisitos do que apenas colher uma semente grande o suficiente.
NPE
2
@SerjArdovic Sim, qualquer material inicial transmitido para um objeto SecureRandom deve ser imprevisível, conforme a documentação Java.
precisa saber é o seguinte
10
@NPE Você está certo, embora uma semente muito pequena seja uma garantia do limite superior, uma semente grande o suficiente não é garantida no limite inferior. Tudo isso faz com a remoção de um limite superior teórico, possibilitando ao RNG gerar todos os 52! combinações.
precisa saber é o seguinte
5
@SerjArdovic O menor número de bytes necessário para isso é 29 (você precisa de 226 bits para representar 52! Combinações possíveis de bits, que são 28,25 bytes, portanto, devemos arredondá-lo). Observe que o uso de 29 bytes de material de semente remove o limite superior teórico do número de shuffles que você poderia obter, sem estabelecer o limite inferior (consulte o comentário da NPE sobre um RNG de baixa qualidade que pega uma semente muito grande e gera uma sequência de todos os zeros).
precisa saber é o seguinte
8
A SecureRandomimplementação quase certamente usará um PRNG subjacente. 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 a documentação diz que a SecureRandomimplementação "cumpre minimamente" certos testes estatísticos e gera resultados "que devem ser criptograficamente fortes", mas não impõe um limite inferior explícito à duração do estado do PRNG subjacente ou ao seu período.)
Peter O.
26

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 48 ; 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 ").

Peter O.
fonte
18

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.

Matt Timmermans
fonte
6
@ ThorstenS, como você pode escrever qualquer tipo de teste que determine que existem combinações de cartas que nunca podem surgir?
Matt Timmermans
2
Existem vários conjuntos de testes de números aleatórios, como Diehard, de George Marsaglia, ou TestU01, de Pierre L'Ecuyer / Richard Simard, que encontram facilmente anomalias estatísticas na saída aleatória. Para verificação de cartão, você pode usar dois quadrados. Você determina o pedido do cartão. O primeiro quadrado mostra a posição das duas primeiras cartas como par xy: A primeira carta como xe a posição da diferença (!) (-26-25) da segunda carta como y. O segundo quadrado mostra a 3ª e a 4ª carta com (-25-25) em relação à 2ª / 3ª. Isso mostrará imediatamente lacunas e agrupamentos em sua distribuição, se você a executar por um tempo.
Thorsten S.
4
Bem, esse não é o teste que você disse que poderia escrever, mas também não se aplica. Por que você supõe que existem lacunas e agrupamentos na distribuição que esses testes revelariam? Isso implicaria uma "fraqueza específica na implementação do PRNG", como mencionei, e não tem nada a ver com o número de sementes possíveis. Esses testes nem exigem que você faça nova propagação do gerador. Eu avisei no início que isso era difícil de entender.
Matt Timmermans
3
@ThorstenS. Esses conjuntos de testes absolutamente não determinarão se a sua fonte é um PRNG criptograficamente seguro de 64 bits ou um RNG verdadeiro. (Afinal, é para testar esses PRNGs.) Mesmo se você conhecesse o algoritmo em uso, um bom PRNG torna inviável determinar o estado sem uma pesquisa de força bruta no espaço de estados.
Sneftel 12/08/19
1
@ ThorstenS .: Em um baralho real, a grande maioria das combinações nunca será exibida. Você simplesmente não sabe quais são esses. Para um PRNG meio decente, é a mesma coisa - se você pode testar se uma determinada sequência de saída que está na sua imagem é uma falha no PRNG. Ridiculamente enorme estado / período como 52! Não é necessário; 128 bits deve ser suficiente.
R .. GitHub Pare de ajudar o gelo
10

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.

Kevin
fonte
9

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.

Thorsten S.
fonte
4

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[]).

IvanK
fonte
3

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 256 - 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]
Artelius
fonte