Pseudoaleatoriedade

Um processo pseudoaleatório é um processo que parece ser aleatório, mas não é. Sequências pseudoaleatórias tipicamente exibem aleatoriedade estatística enquanto estão sendo geradas por um processo inteiramente determinístico. Tal processo é mais fácil de se produzir do que um genuinamente aleatório, e tem o benefício de poder ser utilizado vezes seguidas para produzir exatamente os mesmos números, o que é útil para teste e correção de software.

Para gerar números verdadeiramente aleatórios é necessário o uso de sistemas medições de processos absolutamente não-determinísticos, e estas medições precisam ser precisas e possíveis de serem repetidas. Linux utiliza, por exemplo, vários medidores conhecidos como system timings (como entradas do teclado, E/S, ou o dígito menos significativo de medições de tensão) para produzir uma pool de números aleatórios. Ele tenta constantemente reabastecer este pool, dependendo do seu nível de importância, e, então emitirá um número aleatório. Este sistema é um exemplo, e funciona de maneira similar àqueles que utilizam um hardware gerador de número pseudoaleatório.

História

A geração de números aleatórios tem muitos usos (em sua maioria em estatística, para amostragem aleatória e simulação). Antes da computação moderna, pesquisadores que precisavam de números aleatórios os gerava através de vários meios (dado, cartas, roleta, etc.), ou utilizavam as tabelas de números aleatórios existentes.

A primeira tentativa de prover para os pesquisadores um suprimento pronto de dígitos aleatórios foi feita em 1927, quando a Cambridge University Press publicou uma tabela de 41.600 dígitos desenvolvida por Leonard H.C. Tippet. Em 1947, a RAND Corporation gerou números por meio de uma simulação eletrônica de uma roleta; os resultados foram eventualmente publicados em 1955 como A Million Random Digits with 100,000 Normal Deviates (Um milhão de dígitos aleatórios com 100.000 desvios normais).

John von Neumann foi um pioneiro dos geradores de números aleatórios baseados em computadores. Um contribuidor notável no campo da geração de números pseudoaleatórios para uso prático é um matemático paquistanês Dr. Arif Zaman. Em 1951, Derrick Henry Lehmer inventou o gerador linear congruente, utilizado na maioria dos geradores de números pseudoaleatórios atuais. Com a disseminação do uso dos computadores, geradores de números pseudoaleatórios substituíram as tabelas numéricas, e "verdadeiros" geradores aleatórios (hardwares geradores de números pseudoaleatórios) são utilizados apenas em alguns casos.

Quase aleatório

Uma variável pseudoaleatória é uma variável que é criada por um procedimento determinístico (frequentemente um programa de computador ou uma subrotina) que (geralmente) recebe bits aleatórios como entrada. A cadeia pseudoaleatória irá, tipicamente, ser maior do que a cadeia aleatória original, porém menos aleatória (menor entropia, no sentido aplicado na teoria da informação). Isto pode ser útil para algoritmos aleatórios.

Geradores de números pseudoaleatórios são amplamente utilizados em aplicações como modelagem computacional (e.g., Cadeias de Markov), estatística, design experimental, etc. Alguns deles são suficientemente aleatórios para serem úteis nestas aplicações; muitos não são, e uma sofisticação considerável é necessária para determinar corretamente a diferença para qualquer propósito em particular. O uso não-precavido de geradores de números pseudoaleatórios prontamente disponíveis tem causado danos consideráveis, e por muito tempo sustentados, no valor de um grande número de projetos de pesquisas por muitos anos. O gerador algoritmo RANDU disponível em muitos mainframes por décadas possui erros consideráveis.

Pseudo-aleatoriedade em complexidade computacional

Ver artigo principal: Complexidade computacional

No contexto da Ciência da computação, uma distribuição de probabilidade é dita pseudoaleatória contra uma classe de adversários se não existe adversário desta classe que possa distinguir esta distribuição de uma distribuição uniforme com uma vantagem significante. Esta noção de pseudo-aleatoriedade é estudada pela Teoria da Complexidade Computacional e tem aplicações na Criptografia.

Formalmente, sejam S e T conjuntos finitos e seja F = {f: S → T} ser uma classe de funções. Uma distribuição D sobre S é ε-pseudoaleatória contra F se para todo f em F, a distância estatística entre as distribuições f(X), onde X é uma amostra tirada de D, e f(Y), onde Y é uma amostra tirada da distribuição uniforme de S, é no máximo ε.

Em aplicações típicas, a classe F descreve um modelo de computação com recursos limitados e se está interessado em distribuições D com certas propriedades que sejam pseudoaleatórias contra F. A distribuição D é frequentemente especificada como a saída de um gerador pseudoaleatório.

Criptografia

Ver artigos principais: Chave e Criptografia

Para aplicações como a criptografia, o uso de geradores de números pseudoaleatórios (tanto a partir de hardware ou software ou alguma combinação) é inseguro. Quando valores aleatórios são necessário na criptografia, o objetivo é tornar a mensagem tão difícil de ser quebrada quanto possível, eliminando ou obscurecendo os parâmetros utilizados para encriptar a mensagem (a chave) da mensagem ou do contexto no qual é transmitida. Sequências pseudoaleatórias são determinísticas e reprodutíveis; tudo que é necessário para descobrir e reproduzir uma sequência pseudoaleatória é o algoritmo utilizado para gerá-la e a semente inicial. Então toda a sequência de números é apenas tão poderosa quanto as partes aleatoriamente escolhidas - algumas vezes o algoritmo e a semente, mas geralmente apenas a semente.

Existem muitos exemplos na história das cifras criptográficas, embora haja os casos bons, nos quais escolhas aleatórias não foram aleatórias o suficiente e como consequência direta a segurança foi perdida. Na Segunda Guerra Mundial, a máquina de cifragem japonesa PURPLE utilizada para comunicações diplomáticas é um bom exemplo. Ela foi quebrada consistentemente durante a guerra, principalmente porque os "valores de chave" utilizados eram insuficiente aleatórios. Eles tinham padrões, e estes padrões tornaram qualquer tráfego interceptado prontamente decriptado. Se estas chaves (i. e., as configurações iniciais dos switches na máquina) fossem geradas de maneira imprevisível (i.e., aleatóriamente), este tráfego teria sido muito mais difícil de quebrar, e talvez fossem mesmo seguros em prática.^{[carece de fontes]}

Usuários e designers de sistemas criptográficos são muito cuidadosos ao tratar suas necessidades de aleatoriedade em último caso. Absolutamente nada mudou com a era da criptografia computadorizada, exceto que padrões de dados pseudoaleatórios são mais facilmente descobertos do que em qualquer outra época. Aleatoriedade é, hoje, mais importante do que nunca.

Método de Monte Carlo

Um Método de Monte Carlo é definido como qualquer método que utiliza sequências de números aleatórios para executar uma simulação. Simulações Monte Carlo são aplicadas em muitos tópicos, incluindo cromodinâmica quântica, terapia de câncer com radiação, fluxo de tráfego, evolução estelar e design VLSI. Todas estas simulações exigem o uso de números aleatórios e portanto geradores pseudoaleatório, o que torna a criação de números quase-aleatórios muito importante.

Um exemplo fácil de como um computador faria um método de simulação Monte Carlo é o cálculo de π. Seja um quadrado e um circulo circunscrito a ele, e um ponto aleatoriamente escolhido dentro do quadrado, o ponto estará dentro ou fora do círculo. Se o processo fosse repetido muitas vezes, seria possível ver que a razão entre os pontos aleatórios que caem dentro do círculo e dos que caem fora é proporcional à razão entre a área do círculo e a área do quadrado. A partir dai podemos estimar pi, como mostrado no código em Python abaixo utilizando o pacote SciPy para gerar números pseudoaleatórios com o algoritmo de Mersenne twister (MT19937). Note que este método é uma maneira ineficiente de numericamente aproximar π.

import scipy
N=100000
x_array = scipy.random.rand(N)
y_array = scipy.random.rand(N)
# generate N pseudo-random independent x and y-values on interval [0,1)
N_qtr_circle = sum(x_array**2+y_array**2 < 1)
# Number of pts within the quarter circle x^2 + y^2 < 1 centered at the origin with radius r=1.
# True area of quarter circle is pi/4 and has N_qtr_circle points within it.
# True area of the square is 1 and has N points with in it, hence we approximate pi with
pi_approx = 4*float(N_qtr_circle)/N # Typical values: 3.13756, 3.15156

Veja também

• Número aleatório
• Variável aleatória
• Gerador de números pseudoaleatórios
• Gerador de número pseudoaleatório (hardware)
• Sequência pseudoaleatória

Referências

Ligações externas

• HotBits: Genuine random numbers, generated by radioactive decay
• Random number history
• Using and Creating Cryptographic-Quality Random Numbers
• In RFC 1750, the use of pseudo-random number sequences in cryptography is discussed at length.
• In Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2
• Chapter 8 in Oded Goldreich's Computational Complexity: A Conceptual Perspective (2008).