Um gerador de número pseudoaleatório (do inglês, PRNG, Pseudo-random Number Generator) é um algoritmo normalmente derivado de uma função matemática que gera uma seqüência de números, os quais são aproximadamente independentes um dos outros. A saída da maioria dos geradores de números aleatórios não é verdadeiramente aleatória; ela somente aproxima algumas das propriedades dos números aleatórios. John von Neumann enfatiza com este comentário "Qualquer um que considere métodos aritméticos para produzir dígitos está, certamente, cometendo um pecado". Enquanto números verdadeiramente aleatórios podem ser gerados usando hardware para geração de número aleatório. Alguns exemplos de números aleatórios são: tempo de resposta de requisições de leitura de um disco rígido e tubos de descarga de gás. Número pseudoaleatórios são uma parte crítica da computação moderna, da criptografia até o método de Monte Carlo passando por sistemas de simulação. Uma cuidadosa análise matemática é necessária para assegurar que a geração dos números seja suficientemente "aleatória".
Lista de geradores de números pseudoaleatórios Abaixo, encontra-se uma lista de geradores que marcaram historicamente o campo de estudo do processo de geração de números pseudoaleatórios, seja por sua importância histórica ou por ser um modelo inovador considerando as suas respectivas épocas. Ademais, apesar de serem PRNGs alguns destes podem ser aplicáveis dentro do campo da criptografia. +ModeloAnoAutoresReferênciasDescriçãoQuadrado Médio1946John von NeumannUm PRNG considerado de baixa qualidade mas de grande relevância histórica por ser um dos pioneiros algoritmos.Gerador de Lehmer1951D.H. LehmerTambém conhecido como método Congruencial Linear Multiplicativo e de grande influência neste campo de estudo.Gerador Congruencial Linear1958W.E. ThomsonModelo derivado de Lehmer (1951) de grande influência e demasiado estudado em todo o mundo.Gerador Lagged Fibonacci (LFG)1958G. J. Mitchell; D. P. MooreUm algoritmo altamente influente no campo de estudo de processos de geração de números aleatórios que inspirou outros grandes autores subsequentes como George Marsaglia, o criador do Teste de qualidade de números aleatórios denominado "Diehard", por exemplo.Linear-feedback Shift Register (LFSR)1965R. C. TauswortheUm gerador cujo design influenciou muitos outros PRNGs seguintes. Portanto, muito importante historicamente. Também conhecido como Gerador de Tausworthe.Gerador de Wichmann & Hill1982B. A. Wichmann; D. I. HillUma combinação de três pequenos LCGs, adequados para CPUs de 16 bits. Amplamente usado em muitos programas, por exemplo, foi usado no Excel 2003 e em mais algumas versões posteriores para a função RAND do Excel e foi o gerador padrão na linguagem Python até a versão 2.2. Rule 301983S. WolframGerador baseado em autômatos celulares.Blum-Blum-Shub 1986M. Blum; L. Blum; M. ShubConsiderado um dos geradores mais seguros do ponto de vista criptográfico, sobretudo, devido a implementação em sua fórmula, estudos e conceitos oriundos da teoria dos números.Gerador de Park-Miller1988S. K. Park; K. W. MillerUma implementação específica de um gerador Lehmer, amplamente utilizado porque está incluído em C++ como a função minstd_rand0 de C++11 em diante.MIXMAX1991G. K. Savvidy; N. G. Ter-Arutyunyan-SavvidyÉ um gerador pertencente a classe de gerador linear de congruência matricial, uma generalização do Método Congruencial Linear. A lógica por trás da família de geradores MIXMAX baseia-se nos resultados da teoria ergódica e da mecânica clássica. Add-with-carry (AWC)1991G. Marsaglia; A. ZamanUma modificação dos geradores Lagged-Fibonacci. Subtract-with-borrow (SWB)1991G. Marsaglia; A. ZamanAlgoritmo derivado dos geradores Lagged-Fibonacci.ISAAC 1993R.J. Jenkins Gerador criptograficamente seguro (CSPRNG) desenvolvido por Robert J. Jenkins.Mersenne Twister (MT)1998M. Matsumoto; N. MakotoProvavelmente o PRNG mais conhecido contido nessa lista, principalmente, por ser um algoritmo implementado nas funções RAND nas linguagens de programação Python e R, além de sua grande presença em jogos eletrônicos como em Pro Evolution Soccer (PES).Xorshift2003G. MarsagliaÉ um subtipo muito rápido de geradores LFSR. Marsaglia também sugeriu como uma melhoria o gerador xorwow, no qual a saída de um gerador xorshift é adicionada com uma seqüência Weyl. O gerador xorwow é o gerador padrão na biblioteca CURAND da interface de programação da aplicação nVidia CUDA para unidades de processamento gráfico. Fortuna2003B. Schneier; N. FergusonAlgoritmo considerado criptográficamente seguro. Conhecido por ser um CSPRNG implementado nos sistemas e produtos da Apple.Well equidistributed long-period linear (WELL)2006F. Panneton, P. L'Ecuyer; M. MatsumotoAlgoritmo conhecido por ser complementar ao Mersenne Twister (MT), buscando de forma deliberada cobrir seus pontos limitantes.Advanced Randomization System (ARS)2011J. Salmon, M. Moraes, R. Dror; D. ShawUma versão simplificada da cifra do bloco AES, levando a um desempenho muito rápido no sistema que suporta o AES-NI.Permuted Congruential Generator (PCG)2014M. E. O'NeillUm modelo derivado do Método Congruencial Linear.Random Cycle Bit Generator (RCB)2016R. CookmanO RCB é descrito como um gerador de padrão de bits feito para superar algumas das deficiências com o Mersenne Twister (MT) e a restrição de curto período/ duração de bits dos geradores de turno/módulo. Xoroshiro128+2018D. Blackman; S. VignaUma modificação dos geradores Xorshift de G. Marsaglia, um dos geradores mais rápidos nas CPUs modernas de 64 bits. Os geradores relacionados incluem xoroshiro128**, xoshiro256+ e xoshiro256***. 64-bit MELG (MELG-64)2018S. Harase; T. KimotoUma implementação de geradores F2 lineares de 64 bits com o período primário Mersenne. Squares RNG2020B. WidynskiGerador derivado do método do Quadrado Médio proposto por John von NeumannItamaracá (Ita)2021D.H. PereiraConhecido por ser o primeiro algoritmo PRNG que possui a Função de Valor Absoluto em sua base. Itamaracá apresenta-se também como um modelo simples, rápido e que gera sequências de números aleatórios aperiódicos.
Ver também Gerador de número pseudoaleatório criptograficamente seguro
Ligações externas Como um computador pode gerar um número aleatório?
Categoria:Geradores de números pseudoaleatórios Categoria:Algoritmos