Números primos na prática
Achei números primos pela primeira vez na escola e na época parecia pura memorização. Anos depois, trabalhando com criptografia e algoritmos, percebi que a coisa é bem diferente do que ensinam no fundamental. Não tem segredo, mas tem um monte de gente fazendo confusão constante, então vou explicar como funciona de verdade.
oq sao numeros primos
Um número primo é aquele que só tem dois divisores naturais: ele mesmo e o número 1. O 2 é o único primo par. A partir dali, tudo que vem é ímpar. Isso parece óbvio, mas é onde muita gente trava, porque começa a achar que qualquer ímpar é primo. Não é. O 9 não é primo. O 15 também não. O 21. O 25. O padrão de não ser divisível por nada além de 1 e dele mesmo é simples de testar, mas fica mais complicado quando os números crescem. Testar manualmente até 100 funciona. Até 10.000 você já pensa duas vezes antes de começar.
Eu trabalhava num sistema de geração de chaves RSA há alguns anos quando precisei validar se um número grande era realmente primo. O problema é que existem falsos positivos em certos algoritmos de teste probabilístico. Usei o teste de Miller-Rabin com bases fixas para números abaixo de 3,3 milhões e funcionou perfeitamente, mas para números acima disso, o teste de AKS é o que garante certeza absoluta. Demora mais, mas não erra. A criva de Eratóstenes continua sendo o método mais eficiente para gerar primos até aproximadamente 10 milhões. Acima disso, a coisa muda. Você começa a depender de testes probabilísticos ou algoritmos como Brillhart-Lehmer-Selfridge. Na prática, bibliotecas como a GMP do GNU já fazem isso de forma otimizada. Não reinvente a roda.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Um detalhe que pouca gente mentiona: o teorema dos números primos diz que a densidade de primos próximos de um número n é aproximadamente 1/ln(n). Isso significa que quanto maior o número, mais rarefeitos eles ficam. Entre 1 e 100 há 25 primos. Entre 100 e 200, só 21. Entre 1.000 e 1.100, apenas 14. Se você está implementando um gerador de primos aleatórios, precisa levar isso em conta senão sua distribuição fica enviesada. Também é importante saber que o primo mais alto conhecido atualmente (até onde tenho informação) é um primo de Mersenne encontrado em dezembro de 2018, com 24.862.048 dígitos. Ele foi descoberto pelo Projeto Primeiro Primo Gigante distribuído. Isso dá uma ideia do tamanho que números primos podem alcançar quando você para de brincar com números pequenos.
Como testar se um número é primo
O teste mais básico é tentar dividir o número por todos os inteiros de 2 até a raiz quadrada dele. Se nenhum divisor for exato, o número é primo. Complexidade O(n). Simples e funcional para uso geral. Para produção, o teste de Miller-Rabin é o padrão da indústria. Ele é probabilístico, mas com o número certo de iterações a probabilidade de erro cai para algo ridiculamente baixo — menos de 1 em 4^k onde k é o número de rodadas. Para números usados em criptografia, 40 rodadas é mais do que suficiente.
Se você precisa de certeza absoluta e o número é menor que 3,3 trilhões, existe um conjunto fixo de bases para Miller-Rabin que elimina qualquer ambiguidade. São poucas dezenas de bases e funciona para todo número naquele intervalo. Economiza tempo de cálculo sem sacrificar precisão. Uma pegadinha comum é esqueceria de tratar o 2 e o 3 como casos especiais e começar o loop de divisões a partir do 2. Funciona, mas gasta ciclos testando divisibilidade por 2 e 3 repetidamente. Basta verificar se o número é 2 ou 3, depois pular só pelos ímpares a partir do 5. Reduz o trabalho pela metade.
Outro erro frequente é confundir primos com números primos relativos. Dois números podem ser coprimos (não compartilham fatores além de 1) sem que nenhum deles seja primo. O 8 e o 15 são coprimos, mas nenhum dos dois é primo. Se seu algoritmo depende de primalidade e aceita coprimos no lugar, os resultados vão falhar silenciosamente. Para quem quer uma implementação prática, a biblioteca OpenSSL tem funções como EVP_PKEY_new_from_digest que geram primos para uso criptográfico internamente. Não recomendo escrever seu próprio gerador de primos para produção a menos que você saiba exatamente o que está fazendo. Um erro aqui não quebra seu código, quebra sua segurança.
