Gerador De Números Pseudoaleatórios
Um gerador de número pseudo-aleató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.
Nota: Para o aparato físico, veja Gerador de número pseudoaleatório (hardware).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 pseudo-aleató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".[carece de fontes]
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.
| Modelo | Ano | Autores | Referências | Descrição |
|---|---|---|---|---|
| Quadrado Médio | 1946 | John von Neumann | Um PRNG considerado de baixa qualidade mas de grande relevância histórica por ser um dos pioneiros algoritmos. | |
| Gerador de Lehmer | 1951 | D.H. Lehmer | Também conhecido como método Congruencial Linear Multiplicativo e de grande influência neste campo de estudo. | |
| Gerador Congruencial Linear | 1958 | W.E. Thomson | Modelo derivado de Lehmer (1951) de grande influência e demasiado estudado em todo o mundo. | |
| Gerador Lagged Fibonacci (LFG) | 1958 | G. J. Mitchell; D. P. Moore | Um 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) | 1965 | R. C. Tausworthe | Um gerador cujo design influenciou muitos outros PRNGs seguintes. Portanto, muito importante historicamente. Também conhecido como Gerador de Tausworthe. | |
| Gerador de Wichmann & Hill | 1982 | B. A. Wichmann; D. I. Hill | Uma 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 30 | 1983 | S. Wolfram | Gerador baseado em autômatos celulares. | |
| Blum-Blum-Shub | 1986 | M. Blum; L. Blum; M. Shub | Considerado 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-Miller | 1988 | S. K. Park; K. W. Miller | Uma 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. | |
| MIXMAX | 1991 | G. 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) | 1991 | G. Marsaglia; A. Zaman | Uma modificação dos geradores Lagged-Fibonacci. | |
| Subtract-with-borrow (SWB) | 1991 | G. Marsaglia; A. Zaman | Algoritmo derivado dos geradores Lagged-Fibonacci. | |
| ISAAC | 1993 | R.J. Jenkins | Gerador criptograficamente seguro (CSPRNG) desenvolvido por Robert J. Jenkins. | |
| Mersenne Twister (MT) | 1998 | M. Matsumoto; N. Makoto | Provavelmente 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). | |
| Xorshift | 2003 | G. 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. | |
| Fortuna | 2003 | B. Schneier; N. Ferguson | [carece de fontes] | Algoritmo considerado criptográficamente seguro. Conhecido por ser um CSPRNG implementado nos sistemas e produtos da Apple. |
| Well equidistributed long-period linear (WELL) | 2006 | F. Panneton, P. L'Ecuyer; M. Matsumoto | Algoritmo conhecido por ser complementar ao Mersenne Twister (MT), buscando de forma deliberada cobrir seus pontos limitantes. | |
| Advanced Randomization System (ARS) | 2011 | J. Salmon, M. Moraes, R. Dror; D. Shaw | Uma 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) | 2014 | M. E. O'Neill | Um modelo derivado do Método Congruencial Linear. | |
| Random Cycle Bit Generator (RCB) | 2016 | R. Cookman | O 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+ | 2018 | D. Blackman; S. Vigna | Uma 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) | 2018 | S. Harase; T. Kimoto | Uma implementação de geradores F2 lineares de 64 bits com o período primário Mersenne. | |
| Squares RNG | 2020 | B. Widynski | Gerador derivado do método do Quadrado Médio proposto por John von Neumann | |
| Itamaracá (Ita) | 2021 | D.H. Pereira | Conhecido 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
Referências
Ligações externas
This article uses material from the Wikipedia Português article Gerador de números pseudoaleatórios, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Conteúdo disponibilizado nos termos da CC BY-SA 4.0, salvo indicação em contrário. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Português (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.