Geradores de números pseudoaleatórios

RKA4 JL - Quando observamos o mundo físico, encontramos flutuações aleatórias em toda parte. Podemos gerar números verdadeiramente aleatórios medindo flutuações aleatórias, conhecidas como ruído. Quando medimos esse ruído, conhecido como amostragem podemos obter números. Um, dois, três, quatro. Por exemplo, se medirmos a corrente elétrica da TV estática ao longo do tempo, nós geraremos uma sequência verdadeiramente aleatória. Podemos visualizar essa sequência aleatória desenhando um caminho que muda de direção de acordo com cada número, conhecido como caminhada aleatória. Observe a falta de padrão em todas as escalas. Em cada ponto da sequência, o próximo passo é sempre imprevisível. Processos aleatórios são considerados não determinísticos, uma vez que é impossível determiná-los antecipadamente. As máquinas, por outro lado, são determinísticas. Sua operação é previsível e repetível. Em 1946, John Von Neumann esteve envolvido na execução de cálculos para os militares especificamente envolvidos no projeto da bomba de hidrogênio. Usando o computador chamado ENIAC, ele planejou calcular, repetidamente, aproximações dos processos envolvidos na fissão nuclear. Entretanto, isso exigia acesso rápido para números gerados aleatoriamente, o que poderia ser repetido se necessário. No entanto, ENIAC tinha uma memória interna muito limitada. Não foi possível armazenar sequências aleatórias longas. Assim, Neumann desenvolveu um algoritmo para simular mecanicamente o aspecto de embaralhamento da aleatoriedade, como vemos a seguir. Primeiro, seleciona-se um número verdadeiramente aleatório, chamado de semente. Este número poderia vir da medição de ruído, ou do tempo atual em milissegundos. Em seguida, essa semente é fornecida como entrada, ou input, para um cálculo simples. Multiplica-se a semente por si mesma e, em seguida, retira-se o resultado do meio. Então, você retira o valor da próxima semente. E repete o processo quantas vezes for necessário. Isso é conhecido como "método de quadrados médios" e é apenas o primeiro de uma longa linha de geradores de números pseudoaleatórios. A aleatoriedade da sequência depende apenas da aleatoriedade da semente inicial. Mesma semente, mesma sequência. Então, quais são as diferenças entre a aleatoriedade gerada versus a sequência gerada pseudoaleatoriamente? Vamos representar cada sequência com uma caminhada aleatória. Elas parecem semelhantes até acelerarmos as coisas. A sequência pseudoaleatória deve eventualmente se repetir. Isso ocorre quando o algoritmo atinge uma semente anteriormente usada e o ciclo se repete. O comprimento, antes de se repetir uma sequência pseudoaleatória, é chamado de período. O prazo é estritamente limitado pelo comprimento da semente inicial. Por exemplo, se usarmos uma semente de dois dígitos, então um algoritmo pode produzir, no máximo, cem números antes de reutilizar uma semente e repetir o ciclo. Uma semente de três dígitos pode expandir, no máximo, mil números antes de repetir seu ciclo. E uma semente de quatro dígitos pode expandir, no máximo, 10 mil números antes se repetir. Se usarmos uma sequência grande o suficiente, essa sequência pode se expandir em trilhões e trilhões de dígitos antes de se repetir. A diferença fundamental é importante. Quando você gera números pseudos aleatoriamente, há muitas sequências que não podem ocorrer. Por exemplo, Alice gera uma sequência verdadeiramente aleatória de vinte turnos. É o equivalente a uma seleção uniforme a partir da pilha de todas as possíveis sequências de deslocamentos. Essa pilha é o equivalente a 26 elevado a 20, que é um tamanho astronômico. Se nós ficássemos aqui embaixo e acendêssemos uma lanterna para cima, uma pessoa no topo não veria a luz por cerca de 200 milhões de anos. Compare isso com Alice gerando uma sequência pseudoaleatória de vinte dígitos, usando uma sequência aleatória de quatro dígitos. Agora, isso é equivalente a uma seleção uniforme a partir de 10 mil possíveis sementes iniciais, o que significa que ela só pode gerar 10 mil sequências diferentes, que é uma pequena fração de todas as sequências possíveis. Quando passamos de sequências aleatórias para pseudoaleatórias, encolhemos o espaço-chave a um espaço de sementes muito, muito menor. Assim, para que uma sequência pseudoaleatória seja indistinguível a partir de uma sequência gerada aleatoriamente, ela deve ser impraticável para um computador, para tentar todas as sementes e encontrar a combinação. Isso leva a uma distinção importante em ciência da computação: entre o que é possível versus o que é possível em um período razoável de tempo. Usamos a mesma lógica quando compramos um cadeado de bicicleta. Sabemos que qualquer um pode simplesmente tentar todas as combinações possíveis até encontrar a combinação e abrir o cadeado, mas isso levaria dias. Durante oito horas, assumimos que é praticamente seguro. Com geradores pseudoaleatórios, a segurança aumenta à medida que o comprimento da semente aumenta. Se o computador mais poderoso leva centenas de anos para percorrer todas as sementes, então podemos seguramente assumir que é praticamente seguro, ao invés de perfeitamente seguro. À medida que os computadores se tornam mais rápidos, o tamanho da semente deve aumentar em conformidade. A pseudoaleatoriedade livra Alice e Bob de terem de partilhar sua sequência de mudança aleatória com antecedência. Ao invés disso, eles compartilham a semente aleatória relativamente curta que torna a mesma sequência aleatória maior quando necessário. Mas o que acontece se eles nunca podem se encontrar para compartilhar esta semente aleatória?