O que torna um gerador pseudo-aleatório, de alta qualidade?

8

Lendo esta resposta a esta pergunta do SO: Por que não combinamos geradores de números aleatórios? , Isso fala sobre

PRNG de alta qualidade (Gerador de números aleatórios pseudo)

por isso me faz pensar no que constitui um PRNG de alta qualidade, presumo que você possa resumir como sendo "mais aleatório", mas

  • Pergunta1: Quais qualidades de um PRNG são usadas para descrever quão 'aleatório' ou 'bom' é?

  • Question2: Se você tem um PRNG de 'má qualidade', existe uma maneira de torná-lo com melhor qualidade?

randomness pseudo-random-generators random-number-generator Jose
fonte
Relevante stackoverflow.com/questions/2130621/...
Adriann
2
Você também precisa distinguir PRNGs mundanos dos RNGs criptograficamente seguros.
Adriann
1
Um PRNG é 'melhor' se for mais difícil distinguir sua saída de bits completamente aleatórios.
Yuval Filmus

Respostas:

9

Existem vários critérios para a qualidade de um PRNG:

  • Quão rápido é. Isso inclui a rapidez com que é configurá-lo e a rapidez com que produz um único bit (amortizado).
  • Quão difícil é adivinhar o próximo bit, dado todos os bits anteriores.
  • Quão difícil é distinguir entre a saída do PRNG e os bits verdadeiramente aleatórios.

Os dois últimos critérios estão fortemente relacionados.

Se você tiver um PRNG de baixa qualidade, poderá melhorá-lo com amplificação da dureza . Tire várias cópias do PRNG (usando diferentes teclas aleatórias) e faça XOR junto. Em muitos casos (embora não todos), isso melhorará significativamente sua qualidade.

Yuval Filmus
fonte
Apenas outra pergunta: por que usar um PRNG que causará a mesma sequência se a mesma semente for usada duas vezes, e não apenas obter uma nova semente (clock da CPU, por exemplo) toda vez que um novo número aleatório for necessário? Essa abordagem não seria mais aleatória?
Jose
2
@ Jose Isso é por design. Em muitos casos, você deseja gerar exatamente a mesma sequência várias vezes. Dois exemplos são experimentos de Monte Carlo (que devem ser repetíveis) e criptografia (onde queremos que dois usuários possuam a mesma sequência aleatória, usada como chave).
Yuval Filmus
As experiências de Monte Carlo raramente precisam de um PRNG criptográfico.
Xavier Combelle 01/09
2

Existem considerações práticas: Quão fácil de usar? Quão rápido? Quão fácil é produzir uma sequência diferente de números aleatórios? Quão fácil é reproduzir os números aleatórios (por exemplo, se você gerou 10 bilhões de números aleatórios, pode gerar exatamente os mesmos 10 bilhões de números aleatórios novamente?)

A grande questão: os números gerados se comportam como uma sequência de números aleatórios? O primeiro PRNG que eu já usei tinha a propriedade bizarra de dois valores consecutivos, o segundo era maior com probabilidade de cerca de 0,6. Não é muito aleatório. Assim, você pode executar todos os tipos de testes estatísticos e verificar se o seu gerador de números aleatórios se comporta de maneira aleatória. Quanto mais ele se comporta como aleatório, melhor.

E então vem a aleatoriedade criptográfica. Se eu lhe der os últimos n números aleatórios e tiver conhecimento completo de como o gerador de números aleatórios se comporta, você pode prever o próximo número aleatório? Se sim, isso o torna inadequado em situações em que você tem adversários.

gnasher729
fonte
0

Eu acrescentaria uma distribuição uniforme à lista de qualidades desejadas.

Maciek Łoziński
fonte
É geralmente entendido que um PRNG gera uma distribuição uniforme (ou quase).
vonbrand 03/03