Faça existem geradores de números aleatórios apátridas?

https://stackoverflow.com/questions/203382

03-07-2019
|

Pergunta

Existe uma diferença entre a geração de vários números usando um único gerador de número aleatório (RNG) versus gerar um número por cada gerador e descartá-lo? Não ambas as implementações gerar números que são igualmente aleatório? Existe uma diferença entre as RNG normais e as RNG seguras para isso?

Eu tenho uma aplicação web que é suposto para gerar uma lista de números aleatórios em nome de clientes. Ou seja, os números devem parecem ser aleatória do ponto de vista de cada cliente. Será que isso significa que eu preciso manter uma RNG aleatório separado por sessão cliente? Ou eu posso compartilhar um único RNG em todas as sessões? Ou eu posso criar e descartar uma RNG em uma base per-request?

Atualizar : Esta questão está relacionada com a é um subconjunto de uma sequência aleatória também aleatório?

Solução

Um gerador de números aleatórios tem um estado - que é, na verdade, uma característica necessária. O próximo número "aleatório" é uma função do número anterior e a semente / estado. Os puristas chamá-los de geradores de números pseudo-aleatórios. Os números vão passar por testes estatísticos para aleatoriedade, mas não são - na verdade -. Aleatória

A seqüência de valores aleatórios é finito e se repita.

Pense em um gerador de números aleatórios como baralhar um conjunto de números e, em seguida, tratar-los em uma ordem aleatória. A semente é usada para "embaralhar" os números. Uma vez que a semente é definido, a sequência de números é fixado e muito difícil de prever. Algumas sementes vai repetir mais cedo do que outros.

A maioria dos geradores têm período que é longo o suficiente para que ninguém vai notar que repetir. Um bits 48 do gerador de número aleatório irá produzir várias centenas de milhares de números aleatórios antes de repetir - valor semente com (AFAIK) qualquer de 32 bits.

Um gerador única gerar aleatório-like valores quando você dá a ele uma única semente e deixá-lo vomitar valores. Se você alterar sementes, em seguida, números gerados com o novo valor de semente pode não aparecer aleatório quando comparado com os valores gerados pela semente anterior - todas as apostas estão fora quando você muda sementes. Então, não.

Uma boa abordagem é ter um gerador e "negócio" os números em torno de seus diversos clientes. Não mexa com a criação e descartando geradores. Não mexa com a mudança de sementes.

Acima de tudo, nunca tente escrever seu próprio gerador de números aleatórios. Os geradores embutidos na maioria das bibliotecas de idioma são realmente bom. especialmente os mais modernos que utilizam mais de 32 bits.

Algumas distros Linux têm um dispositivo /dev/random e /dev/urandom. Você pode ler estes uma vez para semear gerador de números aleatórios do seu aplicativo. Estes têm valores mais ou menos aleatórias, mas eles trabalham por "reunir ruído" de eventos do sistema aleatórios. Use-os com moderação por isso há muitos eventos aleatórios entre usos.

Outras dicas

Eu recomendaria usar um único gerador várias vezes. Tanto quanto eu sei, todos os geradores têm um estado. Quando você semear um gerador, você define seu estado para algo baseado na semente. Se você continuar gerando novos, é provável que as sementes que você escolher não vai ser tão aleatório como os números gerados usando apenas um gerador.

Isto é especialmente verdadeiro com a maioria dos geradores que usei, que usam a hora atual em milissegundos como uma semente.

baseado em hardware, é verdade [1], geradores de números aleatórios são possíveis, mas não trivial e muitas vezes têm taxas médias baixas. Availablity também pode ser um problema [2]. Googling para "ruído shot" ou "decaimento radioativo" em combinação com "gerador de números aleatórios" deve retornar alguns hits.

Estes sistemas não é necessário para manter o estado. Provavelmente não o que você estava procurando.

Como conhecida por outros, sistemas de software são apenas pseudo-aleatório, e deve manter o estado.

Um compromisso é usar um hardware baseado RNG para fornecer uma poça de entropia (estado armazenado) que é disponibilizado para semear um PRNG. Isso é feito de forma bastante explícita na implementação Linux de / dev / random [3] e / dev / urandom [4].

Estes alguma discussão sobre o quão aleatória das entradas padrão para o dev / piscina entropia / random realmente são.

Notas de rodapé:

módulo quaisquer problemas com a nossa compreensão da física
porque você está esperando por um processo aleatório
/ dev / características aleatórias de acesso directo à piscina entropia semeado a partir de várias fontes consideradas muito ou quase aleatória e blocos quando a entropia está esgotado
/ dev / urandom é como / dev / random, mas quando o entopy se esgota um hash criptográfico é empregado o que torna a poça de entropia efetivamente um stateful PRNG

Se você criar uma RNG e gerar um único número aleatório a partir dele, em seguida, descartar o RNG, o número gerado é tão aleatório como a semente usada para iniciar o RNG.

Seria muito melhor para criar um único RNG e desenhar muitos números a partir dele.

Como as pessoas já disse, é muito melhor para semear o PRNG uma vez e reutilizá-lo. Um PRNG seguro é simplesmente uma que seja adequada para aplicações criptográficas. A única maneira de re-semear cada vez dará resultados razoavelmente aleatórios é onde ele vem de uma fonte verdadeiramente aleatório "mundo real" - ou seja, hardware especializado. Mesmo assim, é possível que a fonte é tendenciosa e ainda vai ser teoricamente melhor usar o mesmo PRNG mais.

Normalmente semear um novo estado leva bastante tempo para uma PRNG séria, e fazer novos cada vez que realmente não vai ajudar muito. O único caso que eu posso pensar de onde você pode querer mais do que um PRNG é para sistemas diferentes, digamos, em um jogo de casino você tem um gerador para baralhar cartões e um separado para gerar comentários feitos pelos caracteres de controle de computador, desta forma realmente dedicado os usuários não podem adivinhar os resultados com base em comportamentos de caracteres.

Uma boa solução para a semeadura é usar este (Random.org) , eles fornecem aleatório números gerados a partir do ruído atmosférico para livre. Poderia ser uma melhor fonte para semear do que usando o tempo.

Edit: No seu caso, eu definitivamente utilizar um PRNG por cliente, se por nenhuma outra razão do que para bons padrões de programação. De qualquer forma, se você compartilhar um PRNG entre os clientes, você ainda estará fornecendo valores pseudo-aleatórios para cada um, de uma qualidade igual a qualidade do seu PRNG. Então, isso é uma opção viável, mas parece ser uma má política para a programação

Vale a pena mencionar que Haskell é uma linguagem que tenta eliminar totalmente o estado mutável. Para conciliar este objetivo com hard-requisitos como IO (que exige alguma forma de mutabilidade), monads deve ser utilizado para passar a linha de estado a partir de um cálculo para a próxima. Deste modo, Haskell implementa o seu gerador de números pseudo-aleatórios. Estritamente falando, a geração de números aleatórios é inerentemente uma operação de estado, mas Haskell é capaz de esconder este facto, movendo o "mutação" estado para o (>>=) operação de ligação.

Isso provavelmente soa um pouco abstrato, e ele realmente não responder a sua pergunta completamente, mas eu acho que ainda é aplicável. Do ponto de vista teórico, é impossível trabalhar com um RNG sem envolver estado. Independentemente disso, existem técnicas que podem ser usadas para mitigar essa interação e torná-lo aparecer , como se toda a operação é de uma natureza sem estado.

Em geral, é melhor criar um único PRNG e puxe vários valores a partir dele. Criar várias instâncias significa que você precisa para garantir que as sementes para as instâncias são garantidos única, o que exigirá incorporando informações específicas do caso.

Como um aparte, há melhor "verdadeiros" geradores de números aleatórios, mas eles geralmente requerem hardware especializado que faz coisas como dados aleatórios Derivar variância sinal elétrico dentro do computador. A menos que você está realmente preocupado com isso, eu diria que os geradores de números aleatórios Pseudo construído nas bibliotecas de língua e / ou OS são provavelmente suficientes, desde que o seu valor de semente não é facilmente previsível.

O uso de um PRNG seguro depende da sua aplicação. Quais são os números aleatórios usados ??para? Se eles são algo de valor real (por exemplo, qualquer coisa cryptographically relacionados), você não iria querer usar nada menos.

PRNGs seguros são muito mais lento, e pode exigir bibliotecas para fazer a operação de precisão arbitrária, e teste de primalidade, etc etc ...

Bem, contanto que eles são semeados de forma diferente cada vez que eles são criados, então não, eu não acho que haveria alguma diferença; no entanto, se dependesse de algo como o tempo, então eles provavelmente seria não uniforme, devido à semente tendenciosa.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow