Todo mundo sabe que um número primo é aquele que não pode ser feito multiplicando outros números inteiros juntos. Esse atributo enganosamente simples esconde um mundo de complexidade que envolveu matemáticos antigos e modernos. Essa qualidade dos primos também tem aplicações essenciais na ciência da computação e no reino da criptografia.
O Teorema Fundamental da Aritmética
Como o próprio nome indica, o Teorema Fundamental da Aritmética diz algo profundo sobre a maneira como os números se comportam. Ele diz que todo número pode ser descrito como o produto de um conjunto específico de primos multiplicados juntos. Este é um resultado curioso que vem da definição básica de primo. Eu digo "curioso" porque é ao mesmo tempo um fato surpreendente e útil: um resultado um tanto oculto, mas também quase direto, da definição de primo.
Esse tipo de manobra mental, em que você pega as propriedades de objetos matemáticos e continua extrapolando suas ramificações, leva eventualmente a algoritmos criptográficos essenciais como Diffie-Hellman, RSA e curva elíptica.
O Teorema Fundamental da Aritmética nos diz que todo número (além de 1) é primo em si mesmo ou o produto único de primos. Como um exemplo simples, considere o número 25:
25 = 5 * 5
Em outras palavras, a "assinatura prima" de 25 é 5 * 5. Apenas 25 tem essa assinatura e 5 * 5 só dá 25. Se você pensar em todo o intervalo de números inteiros — isto é, a infinitude de números inteiros — verá que o teorema nos garante um enorme espaço de instâncias exclusivamente identificáveis.
Pegue um número arbitrário e faça a pergunta: Qual é sua fatoração prima? Ou seja, qual é sua assinatura prima? A resposta para essa pergunta acaba sendo muito difícil, especialmente quando comparada com a operação inversa, de criar um número que é o produto de dois primos conhecidos.
O teorema fundamental sustenta essa dificuldade porque significa que em todo o espaço de números, cada número tem apenas um conjunto de fatores primos. Isso também significa que atacar esses problemas por força bruta não é viável. Para 25, é claro, você pode simplesmente descobrir 5 * 5, mas e um número com mil dígitos? É computacionalmente inviável adivinhar os fatores.
Primos em funções hash
Outra área interessante onde primos aparecem na codificação é a criação de funções hash. Em uma função hash, o trabalho principal é pegar uma entrada e transformá-la em um número que fique em seu lugar. O número é uma redução da entrada geral, e esse fato o torna útil para muitas coisas, como somas de verificação e estruturas como tabelas hash.
O hash para uma hashtable (a função hash para o objeto que está sendo colocado na coleção; ou seja, Java's hashCode) usa um módulo de uma constante, e essa constante é recomendada para ser um primo. Nesse caso, usar um primo para a constante pode ajudar a reduzir a probabilidade de colisões. Isso ocorre porque a primocidade do número contribui para uma distribuição mais uniforme do módulo, porque há menos denominadores comuns com a função da hashtable.
Pelo mesmo motivo, um primo na "contagem de buckets" da hashtable ajuda a evitar colisões assimétricas. Em essência, usar primos na constante de hash e na contagem de buckets ajuda a garantir uma boa distribuição aleatória de itens em buckets, reduzindo a probabilidade de relacionamentos significativos entre os dois.
A discussão sobre esse relacionamento no Stack Overflow é um bom ponto de partida para investigações futuras sobre o tópico de primos e hashes.
Outro terreno fértil para primos e hashing trabalhando juntos é em funções como SHA-256 e MD5. Elas são usadas em todo lugar para coisas como hash de senhas e como elementos de criptomoeda. SHA 256 do zero com caneta e papel é um passo a passo divertido de fazer SHA-256 manualmente, como parte do processo de construção de uma chave Bitcoin do zero. Ele destaca o papel que os primos desempenham.
Primos e matemática modular
Outra área fascinante da matemática com muitas implicações para a programação é a matemática modular. Às vezes, ela é chamada de "matemática do relógio" porque pega um intervalo finito de números e conta apenas o que sobra. Um exemplo é a maneira como usamos os números de 1 a 12 no relógio e usamos apenas o excesso, de modo que 13 horas se tornam 1 hora (assumindo que começamos às 12).
A matemática modular surge em muitas áreas, especialmente na criptografia, e usar primos com ela é frequentemente necessário para atingir as propriedades necessárias, como ter um inverso multiplicativo. A Cambridge University Press tem uma ótima análise de primos como módulos.
Crivo de Eratóstenes
Agora, vamos inverter um pouco as coisas e ver como a codificação nos ajuda a lidar e entender um dos problemas clássicos da matemática: descobrir a primosidade. Um algoritmo antigo foi descrito por Eratóstenes, trabalhando no século III a.C. O algoritmo, agora chamado de Crivo de Eratóstenes, fornece um conjunto de etapas para encontrar todos os primos para um determinado número.
A ideia básica por trás do algoritmo é pegar um número, n, e através de uma série de passagens, eliminar os números não primos. O que resta quando você termina é o conjunto de primos que você está procurando. Há muitas maneiras possíveis de refinar esse processo, mas a versão moderna básica da peneira começa pegando 2 e anotando-o como primo, então encontrando todos os números pares até n, anotando-os como não primos. Então, passamos para 3 e fazemos a mesma coisa para múltiplos de 3. Continuando, fazemos o mesmo para todos os números até n, apenas pulando aqueles números que já anotamos como não primos.
A Hipótese de Riemann
Um dos problemas não resolvidos mais interessantes em matemática é a Hipótese de Riemann (aqui está a base de código para calculá-la). Riemann foi aluno de Gauss, cujo nome você pode conhecer do "borrão gaussiano" em softwares como o Adobe Photoshop. Gauss criou uma função para estimar a ocorrência de primos, conhecida agora como Teorema dos Números Primos. A função de Reimann, chamada de função zeta, incorpora números complexos em sua série infinita e aumenta a precisão do teorema de Gauss. A Hipótese de Riemann lança luz sobre o comportamento fundamental dos números, e como isso impacta a ciência da computação é uma questão em aberto. Provar a hipótese é talvez o esforço mais proeminente em matemática teórica.
Alan Turing é provavelmente a figura mais conhecida no ponto em que a matemática e a computação se encontram. Ele tinha um longo e profundo relacionamento com primos e, em particular, com a Hipótese de Riemann. Ele estava trabalhando na construção de uma máquina de Hipótese de Riemann quando foi interrompido pela eclosão da Segunda Guerra Mundial, onde aplicou lições daquele esforço à tarefa de construir uma máquina analítica para quebrar as cifras nazistas.
