Como funcionam os geradores de números aleatórios?

A resposta curta

Um computador segue instruções exatamente, então não consegue inventar aleatoriedade do nada. Ou ele calcula números que passam em testes estatísticos de aleatoriedade (um gerador de números pseudoaleatórios, PRNG), ou ele mede algo fisicamente imprevisível e processa isso (uma fonte aleatória verdadeira ou de hardware). Os sistemas modernos combinam as duas coisas: o sistema operacional reúne ruído imprevisível e usa esse ruído como semente de um PRNG criptograficamente seguro (CSPRNG), que então produz quantos números forem necessários.

O gerador desta página usa a fonte segura do navegador pela Web Crypto API e converte o resultado para o seu intervalo sem viés. Digite um Mínimo e um Máximo, escolha a Quantidade e clique em Gerar.

Geradores pseudoaleatórios e sementes

Um PRNG guarda um estado interno. Cada vez que você pede um número, ele embaralha o estado com uma fórmula fixa e entrega parte do resultado. O modelo clássico mais simples, o gerador congruencial linear, calcula o próximo estado como (a vezes o estado mais c) módulo m. Modelos melhores, como o Mersenne Twister (o padrão do módulo random do Python) ou a família xorshift, produzem sequências de qualidade muito maior, e o Mersenne Twister só se repete depois de 2 elevado a 19.937 menos 1 passos.

A semente é o estado inicial. A mesma semente sempre produz a mesma sequência. Em muitas situações isso é uma vantagem, não um defeito: um cientista pode repetir uma simulação exatamente, um jogo pode reconstruir um mundo inteiro a partir de um código curto de semente, e um teste pode reproduzir um bug. Mas se um programa usa como semente algo fácil de adivinhar, como a hora atual em segundos, um atacante pode testar todas as sementes prováveis e recriar os números.

Pseudoaleatório ou criptograficamente seguro

Os PRNGs rápidos de uso geral são bons estatisticamente, mas previsíveis: depois de observar saídas suficientes, é possível reconstruir o estado interno e prever todos os números seguintes. Isso não tem problema para um efeito de partículas em um jogo, mas tem para uma senha, um sorteio ou um token de segurança.

Onde os computadores encontram aleatoriedade de verdade

Os sistemas operacionais coletam pequenos eventos imprevisíveis: o momento exato das interrupções, a atividade de disco e de rede, e geradores de hardware dedicados, presentes em muitos processadores modernos, que medem ruído elétrico. Essa entropia é misturada em um reservatório e usada para dar a semente inicial e renovar regularmente um CSPRNG. O Linux oferece isso por getrandom e /dev/urandom, e o Windows pelas funções de criptografia do sistema.

Alguns serviços vão além, por publicidade ou para ter garantia extra. O Random.org usa ruído de rádio atmosférico, e a Cloudflare ficou famosa por filmar uma parede de luminárias de lava como uma das suas fontes de entropia. Para o dia a dia, o gerador do sistema operacional já é forte o bastante até para chaves de criptografia.

Como os navegadores geram números aleatórios seguros

O JavaScript tem duas opções. Math.random() devolve um número entre 0 e 1 vindo de um PRNG rápido (os motores atuais usam algoritmos do tipo xorshift). Ele serve para animações, mas não foi feito para ser imprevisível, e a especificação não promete nenhuma segurança.

crypto.getRandomValues() preenche um array com bytes aleatórios do CSPRNG do navegador, que recebe a semente do sistema operacional. Ele existe em todos os navegadores modernos, funciona offline e é o que geradores de senha e códigos de geração de chaves deveriam usar. Uma única chamada devolve no máximo 65.536 bytes, então trabalhos grandes chamam a função várias vezes. Este gerador, assim como o cara ou coroa, o rolador de dados, a roleta e o sorteador de nomes do Anyfeat, usa crypto.getRandomValues.

Por que rand() % n pode ter viés

Um gerador entrega valores brutos em uma faixa fixa, por exemplo um byte de 0 a 255. O jeito óbvio de conseguir um número de 0 a 5 é pegar o resto da divisão por 6 (valor % 6). O problema: 256 valores não se dividem igualmente em 6 grupos. 256 é 42 vezes 6 mais 4, então os restos de 0 a 3 aparecem 43 vezes cada e os restos 4 e 5 só 42 vezes. Alguns resultados ficam cerca de 2,4% mais prováveis que outros. Isso se chama viés do módulo (modulo bias).

Com valores de 32 bits e um intervalo pequeno, o viés fica minúsculo, mas com intervalos grandes ele cresce. A correção padrão é a amostragem por rejeição: encontre o maior múltiplo de n que cabe na faixa bruta (252 no exemplo do byte), descarte qualquer valor bruto igual ou acima dele e sorteie de novo. Todos os valores que sobram se distribuem igualmente no intervalo. Este gerador sorteia valores de 32 bits e rejeita a sobra desigual, então cada número do seu intervalo tem exatamente a mesma probabilidade.

Um erro parecido é usar Math.floor(Math.random() * n) para fins de segurança. O arredondamento funciona para a maioria dos intervalos, mas a fonte é previsível, então não deve ser usada para senhas ou sorteios que valem dinheiro.

Números únicos, embaralhamentos e armadilhas comuns

• Números únicos: para sortear sem repetição, embaralhe o intervalo inteiro com o algoritmo de Fisher Yates e pegue os k primeiros, ou sorteie e descarte as repetições. Este gerador faz exatamente isso quando Sem repetição está marcado, e avisa se o intervalo for pequeno demais para a quantidade.
• Embaralhamentos com viés: ordenar uma lista com uma função de comparação aleatória não dá um embaralhamento uniforme. Use Fisher Yates.
• Renovar a semente com frequência demais: usar a hora como semente de um PRNG dentro de um loop pode produzir o mesmo número muitas vezes seguidas.
• Decimais: escolher um decimal aleatório escalando uma fração aleatória pode deixar as pontas do intervalo menos prováveis. Esta ferramenta sorteia um número inteiro de passos (com 2 casas decimais, centésimos), então as duas pontas entram com a mesma chance.
• Esperar que não haja padrões: uma saída realmente aleatória tem sequências e repetições. Ver o 7 duas vezes seguidas não é sinal de gerador quebrado.