Gerador de primo aleatório

Como usar Gerador de primo aleatório

Números primos são os átomos da matemática dos inteiros. Euclides provou, por volta de 300 a.C., que existem infinitos primos — uma das demonstrações matemáticas mais elegantes já escritas, usando apenas três linhas de lógica. Todo número inteiro maior que 1 pode ser decomposto de forma única como produto de primos (o Teorema Fundamental da Aritmética), tornando os primos a base sobre a qual toda a teoria dos números é construída. Por milênios, eles foram objeto de curiosidade puramente matemática. Então, em 1977, três cientistas do MIT publicaram um artigo que mudou o mundo: Ron Rivest, Adi Shamir e Leonard Adleman descreveram o RSA — o primeiro algoritmo prático de criptografia de chave pública, cuja segurança depende inteiramente da dificuldade de fatorar o produto de dois primos grandes.

O RSA funciona assim: escolha dois primos grandes, p e q, e multiplique-os para obter n. Publicar n é seguro — mas fatorar n de volta em p e q, quando eles têm centenas de dígitos, é computacionalmente inviável com os algoritmos conhecidos. A chave pública usa n; as operações privadas usam p e q. Esse princípio — operações fáceis de fazer e difíceis de desfazer — chama-se função de mão única, e está na base de praticamente toda a criptografia assimétrica moderna. O protocolo Diffie-Hellman, que protege a troca de chaves TLS toda vez que você acessa um site HTTPS, também usa primos: a segurança depende da dificuldade do logaritmo discreto em grupos de ordem prima. Primos não são apenas curiosidade matemática — eles guardam seus dados bancários, seus e-mails e sua VPN.

Encontrar primos de forma eficiente é um problema computacional interessante. A abordagem ingênua — dividir n por todos os inteiros até √n — é correta mas impraticável para números grandes. O Crivo de Eratóstenes, inventado há mais de 2.200 anos, resolve o problema para faixas menores com elegância: marca os múltiplos de cada primo e o que sobra são os primos. Para verificar se um número muito grande é primo, algoritmos probabilísticos como Miller-Rabin são usados: eles reduzem a probabilidade de erro a qualquer limite desejado com cada iteração adicional. O OpenSSL usa Miller-Rabin para gerar os primos das chaves RSA. Esta ferramenta aplica verificação determinística para a faixa configurável — explore a distribuição dos primos, observe como eles ficam mais espaçados em faixas maiores, e lembre que cada conexão HTTPS que você fez hoje dependeu de primos como esses.