Esta é uma tradução automática e o texto original em inglês é a versão de referência. Ler o original
Os primos escasseiam a uma taxa definível
Perto de um número de 1024 bits, um em cada 355 números ímpares é primo. Não se trata de uma probabilidade reduzida, o que é a única razão pela qual a criptografia de chave pública é possível.
Existem 25 primos abaixo de 100, 168 abaixo de 1000 e 78.498 abaixo de um milhão. As contagens diminuem, mas nunca param, e o ritmo a que escasseiam é um dos factos mais úteis da matemática.
Um em ln n
Perto de um número n, aproximadamente um em cada ln n números é primo. Abaixo de 100, isso prevê 100 / ln 100 = 21,7 primos, e o Prime Sieve mostra exatamente esse valor ao lado da contagem real de 25, juntamente com o erro de 13,1%.
A estimativa é rudimentar aqui, mas melhora. Num milhão, N / ln N resulta em 72.382 contra os 78.498 reais, um erro de 7,8%. O erro relativo diminui à medida que N cresce, o que constitui o verdadeiro conteúdo do teorema dos números primos.
A melhor estimativa que parece pior
A ferramenta apresenta uma segunda aproximação, Li(N), o integral logarítmico. Em N = 100, dá 29,1 e é pior do que a rudimentar: um erro de 16,3% contra 13,1%.
Quem lesse apenas essa linha concluiria que a fórmula mais elaborada não vale a pena. Ao alterar N, a ordenação inverte-se e nunca mais volta atrás:
- N = 100: N/lnN com um erro de 13,1%, Li com um erro de 16,3%
- N = 1000: N/lnN com um erro de 13,8%, Li com um erro de 5,1%
- N = 10⁶: N/lnN com um erro de 7,8%, Li com um erro de 0,16%
O Li não é tanto um refinamento de N / ln N, mas sim a sua versão rigorosa. A fórmula rudimentar aplica a densidade em n a todo o intervalo de 0 a n, quando a densidade perto de 2 é muito diferente da densidade perto de um milhão. O Li integra 1/ln t ao longo do intervalo em vez de a presumir constante, e a recompensa é um erro de uma parte em seiscentas, onde o atalho ainda falha por 8%.
Uma única avaliação de uma aproximação nada nos diz sobre se ela é boa. É necessário observar o seu comportamento à medida que o valor de entrada cresce.
Por que razão nunca se esgotam
Porque 1/ln n diminui lentamente. A sua soma diverge, pelo que os primos escasseiam, mas não o suficiente para serem finitos.
A demonstração de Euclides é mais direta e mais antiga. Tome-se uma lista finita qualquer de primos, multipliquem-se todos e adicione-se um. O resultado deixa resto 1 quando dividido por qualquer primo da lista, pelo que todos os seus fatores primos estão ausentes da lista. Nenhuma lista finita pode estar completa.
As outras duas leituras da ferramenta mostram o quanto ainda está por esclarecer. Conta 8 pares de primos gémeos abaixo de 100 e indica 8 como a maior lacuna. Se os pares de primos gémeos continuam infinitamente permanece por provar, assim como a conjetura de que existe sempre um primo entre quadrados consecutivos.
O número que determina o tamanho de uma chave
Gerar uma chave RSA implica encontrar primos de grande dimensão, e o método consiste em escolher um número ímpar aleatório com o tamanho adequado e testá-lo.
O tempo que isso demora é precisamente a questão da densidade. Um número de 1024 bits está próximo de 2¹⁰²⁴, e ln(2¹⁰²⁴) = 1024 × ln 2 = 710. Portanto, cerca de um em cada 710 números nessa região é primo e, como apenas se testam candidatos ímpares, um em cada 355.
Trezentas e cinquenta e cinco tentativas, cada uma delas um teste de primalidade probabilístico rápido. É por isso que a geração da chave demora um instante em vez de uma era geológica, e todo o dimensionamento resulta de um logaritmo. Aumentando o expoente, o custo cresce linearmente com o número de bits, motivo pelo qual as chaves de 2048 bits e de 4096 bits continuam a ser práticas.
Se os primos tivessem escasseado mesmo que ligeiramente mais depressa, por exemplo como 1/n, a busca seria sem esperança e a internet teria sido construída sobre outra base qualquer.
Ninguém prova os primos que utiliza
Um detalhe torna as 355 tentativas baratas: o teste não estabelece a primalidade.
O teste de Miller-Rabin escolhe uma testemunha aleatória e faz uma pergunta a que todos os primos respondem da mesma forma. Um número composto pode responder como se fosse primo, mas no máximo um quarto das testemunhas possíveis permitirá que tal aconteça, pelo que cada ronda independente reduz a probabilidade de erro por um fator de pelo menos quatro. Quarenta rondas deixam um pior cenário abaixo de 4⁻⁴⁰, o que se situa em torno de 10⁻²⁴.
Isso está muito abaixo da probabilidade de ocorrer um erro de memória não detetado na máquina que executa a aritmética. As chaves que protegem o tráfego mundial assentam em números que são quase de certeza primos, e a dúvida residual é inferior à do próprio hardware.