Um número pseudo-aleatório é um número especial gerado por um gerador especial. O Deterministic Random Bit Generator (PRNG), também conhecido como Deterministic Random Bit Generator (DRBG), é um algoritmo para gerar uma sequência de números cujas propriedades se aproximam das características das sequências de números aleatórios. A sequência PRNG gerada não é verdadeiramente aleatória, pois é inteiramente determinada por um valor de semente chamado de semente PRNG, que pode incluir valores verdadeiramente aleatórios. Embora sequências mais próximas do aleatório possam ser geradas usando geradores de números aleatórios de hardware, geradores de números pseudo-aleatórios são importantes na prática para a velocidade de geração de números e sua reprodutibilidade.
Aplicativo
PRNGs são centrais para aplicações como simulação (por exemplo, para Monte Carlo), jogos eletrônicos (por exemplo, para geração procedural) e criptografia. Os aplicativos criptográficos exigem que a saídaos dados não eram previsíveis a partir de informações anteriores. São necessários algoritmos mais complexos que não herdam a linearidade de PRNGs simples.
Termos e Condições
Boas propriedades estatísticas são um requisito central para a obtenção de um PRNG. Em geral, é necessária uma análise matemática cuidadosa para garantir que o RNG gere números que sejam próximos o suficiente do aleatório para serem apropriados para o uso pretendido.
John von Neumann advertiu contra a interpretação errônea do PRNG como um gerador verdadeiramente aleatório e brincou que "Qualquer um que considere métodos aritméticos para gerar números aleatórios certamente está em estado de pecado."
Usar
PRNG pode ser iniciado a partir de um estado inicial arbitrário. Sempre irá gerar a mesma sequência quando inicializado com este estado. O período PRNG é definido da seguinte forma: máximo em todos os estados iniciais do comprimento do prefixo de sequência não repetitiva. O período é limitado pelo número de estados, geralmente medido em bits. Como o comprimento do período potencialmente dobra com cada bit de "estado" adicionado, é fácil criar PRNGs com períodos grandes o suficiente para muitas aplicações práticas.
Se o estado interno do PRNG contém n bits, seu período não pode ser superior a 2n resultados, é muito menor. Para alguns PRNGs, a duração pode ser calculada sem ignorar todo o período. Os registradores de deslocamento de realimentação linear (LFSRs) são tipicamentesão escolhidos de modo a ter períodos iguais a 2n − 1.
Geradores congruentes lineares têm períodos que podem ser calculados usando fatoração. Embora a PPP repita seus resultados após atingir o final do período, um resultado repetido não significa que o final do período foi atingido, pois seu estado interno pode ser maior que a saída; isso é especialmente evidente para PRNGs com saída de bit único.
Possíveis erros
Os erros encontrados por PRNGs defeituosos variam de sutis (e desconhecidos) a óbvios. Um exemplo é o algoritmo de número aleatório RANDU, que tem sido usado em mainframes por décadas. Foi uma falha séria, mas sua inadequação passou despercebida por um longo período de tempo.
Em muitas áreas, estudos de pesquisa que usaram seleção aleatória, simulações de Monte Carlo ou outros métodos baseados em RNG são muito menos confiáveis do que poderiam ser o resultado de GNPG de baixa qualidade. Ainda hoje, às vezes é necessário cautela, como evidenciado pelo aviso na Enciclopédia Internacional de Ciência Estatística (2010).
Estudo de caso bem sucedido
Como ilustração, considere a linguagem de programação Java amplamente utilizada. A partir de 2017, Java ainda conta com o Linear Congruential Generator (LCG) para seu PRNG.
Histórico
O primeiro PRNG para evitar problemas sérios e ainda rodar bem rápido,foi o Mersenne Twister (discutido abaixo), que foi publicado em 1998. Desde então, outros PRNGs de alta qualidade foram desenvolvidos.
Mas a história dos números pseudo-aleatórios não termina aí. Na segunda metade do século 20, a classe padrão de algoritmos usados para PRNGs incluía geradores lineares congruentes. A qualidade do LCG era sabidamente inadequada, mas métodos melhores não estavam disponíveis. Press et al (2007) descreveram o resultado da seguinte forma: "Se todos os artigos científicos cujos resultados estão em dúvida por causa de [LCGs e relacionados] desaparecessem das prateleiras das bibliotecas, haveria uma lacuna do tamanho do seu punho em todas as prateleiras."
A principal conquista na criação de geradores pseudo-aleatórios foi a introdução de métodos baseados em recorrentes lineares em um corpo de dois elementos; tais osciladores são acoplados a registradores de deslocamento de realimentação linear. Eles serviram de base para a invenção de sensores de números pseudo-aleatórios.
Em particular, a invenção de 1997 por Mersen Twister evitou muitos dos problemas com geradores anteriores. O Mersenne Twister tem um período de 219937−1 iterações (≈4,3 × 106001). Foi comprovado que ele é distribuído uniformemente em (até) 623 dimensões (para valores de 32 bits) e, no momento de sua introdução, era mais rápido do que outros geradores estatisticamente sólidos que produzem sequências numéricas pseudo-aleatórias.
Em 2003, George Marsaglia introduziu uma família de geradores xorshift também baseados em repetição linear. Esses geradores são extremamentesão rápidos e - combinados com uma operação não linear - passam por rigorosos testes estatísticos.
Em 2006, a família de geradores WELL foi desenvolvida. Os geradores WELL de certa forma melhoram a qualidade do Twister Mersenne, que tem um espaço de estado excessivamente grande e uma recuperação muito lenta deles, gerando números pseudo-aleatórios com muitos zeros.
Criptografia
PRNG adequado para aplicações criptográficas é chamado de PRNG criptograficamente seguro (CSPRNG). O requisito para um CSPRNG é que um invasor que não conheça a semente tenha apenas uma vantagem marginal em distinguir a sequência de saída do gerador de uma sequência aleatória. Em outras palavras, enquanto um PRNG só é necessário para passar em certos testes estatísticos, um CSPRNG deve passar em todos os testes estatísticos limitados ao tempo polinomial no tamanho da semente.
Embora a prova desta propriedade esteja além do nível atual da teoria da complexidade computacional, fortes evidências podem ser fornecidas reduzindo o CSPRNG a um problema considerado difícil, como a fatoração de inteiros. Em geral, podem ser necessários anos de revisão antes que um algoritmo possa ser certificado como CSPRNG.
Foi demonstrado que é provável que a NSA tenha inserido uma porta traseira assimétrica no gerador de números pseudo-aleatórios Dual_EC_DRBG certificado pelo NIST.
Algoritmos pseudo-aleatóriosnúmeros
A maioria dos algoritmos PRNG produz sequências que são distribuídas uniformemente por qualquer um dos vários testes. Esta é uma pergunta aberta. É uma das centrais na teoria e prática da criptografia: existe uma maneira de distinguir a saída de um PRNG de alta qualidade de uma sequência verdadeiramente aleatória? Nessa configuração, o resolvedor sabe que um algoritmo PRNG conhecido foi usado (mas não o estado com o qual foi inicializado) ou um algoritmo verdadeiramente aleatório foi usado. Ele deve distinguir entre eles.
A segurança da maioria dos algoritmos e protocolos criptográficos que usam PRNGs é baseada na suposição de que é impossível distinguir entre o uso de um PRNG adequado e o uso de uma sequência verdadeiramente aleatória. Os exemplos mais simples dessa dependência são as cifras de fluxo, que geralmente funcionam omitindo ou enviando a mensagem de texto simples com uma saída PRNG, produzindo o texto cifrado. Projetar PRNGs criptograficamente adequados é extremamente difícil, pois eles devem atender a critérios adicionais. O tamanho de seu período é um fator importante na adequação criptográfica de um PRNG, mas não o único.
Um dos primeiros PRNGs de computador propostos por John von Neumann em 1946 é conhecido como o método dos quadrados médios. O algoritmo é o seguinte: pegue qualquer número, eleve ao quadrado, remova os dígitos do meio do número resultante como um "número aleatório" e use esse número como o número inicial para a próxima iteração. Por exemplo, a quadratura do número 1111 dá1234321, que pode ser escrito como 01234321, um número de 8 dígitos é o quadrado de um número de 4 dígitos. Isso dá 2343 como um número "aleatório". O resultado da repetição desse procedimento é 4896 e assim por diante. Von Neumann usou números de 10 dígitos, mas o processo foi o mesmo.
Desvantagens do "quadrado do meio"
O problema com o método do "quadrado médio" é que todas as sequências eventualmente se repetem, algumas muito rapidamente, por exemplo: 0000. Von Neumann sabia disso, mas encontrou uma abordagem suficiente para seus propósitos e se preocupou que o "correções" matemáticas apenas ocultariam os erros em vez de removê-los.
Von Neumann encontrou geradores de números aleatórios e pseudo-aleatórios de hardware inadequados: se eles não gravarem a saída gerada, não poderão ser verificados quanto a erros posteriormente. Se eles escrevessem seus resultados, eles esgotariam a memória limitada disponível do computador e, portanto, a capacidade do computador de ler e escrever números. Se os números fossem escritos em cartões, levariam muito mais tempo para serem escritos e lidos. No computador ENIAC ele usou o método do "quadrado do meio" e realizou o processo de obtenção de números pseudo-aleatórios várias centenas de vezes mais rápido do que a leitura de números de cartões perfurados.
Quadrado médio foi substituído por geradores mais complexos.
Método inovador
Uma inovação recente é combinar o quadrado médio com a sequência de Weil. Este método garante produtos de alta qualidade dentro delongo período. Ajuda a obter as melhores fórmulas de números pseudo-aleatórios.
