Um número primo $p$ é um primo de Sophie Germain quando $2p+1$ também é primo. O $5$ é, porque $11$ é primo. O $7$ não é, porque $15=3\cdot5$. A lista começa assim:

$$2,\ 3,\ 5,\ 11,\ 23,\ 29,\ 41,\ 53,\ 83,\ 89,\ 113,\ 131,\ldots$$

O primo $2p+1$ que acompanha cada um é chamado de primo seguro: $5, 7, 11, 23, 47, 59, 83, \ldots$ Sophie Germain precisou deles para o seu teorema sobre Fermat. Dois séculos depois, eles protegem as conexões da internet.

Será que acabam?

Abaixo de 100 há 10 primos de Sophie Germain; abaixo de 1000, 37. Eles vão ficando mais raros, mas continuam aparecendo. Ninguém sabe provar que são infinitos. É um problema em aberto, da mesma família da conjectura dos primos gêmeos, que pergunta se há infinitos pares de primos como $11$ e $13$, que diferem por 2.

Correntes

Às vezes dá para repetir a operação. Começando em $2$:

$$2\to5\to11\to23\to47,$$

todos primos, até que $2\cdot47+1=95$ não é. Uma sequência assim se chama cadeia de Cunningham, em homenagem ao militar e matemático britânico Allan Cunningham, que as estudou no início do século XX. A cadeia de 89 também é longa: $89\to179\to359\to719\to1439\to2879$, seis primos seguidos.

Um teorema de Euler e Lagrange

Os números de Mersenne $2^p-1$ são os candidatos favoritos a primos gigantes. Euler enunciou, e Lagrange provou em 1775, que os primos seguros podem estragar a festa:

Se $p$ é um primo de Sophie Germain com $p\equiv3\pmod4$, então $2p+1$ divide $2^p-1$.

Para $p=11$, temos $2p+1=23$, e de fato $2^{11}-1=2047=23\cdot89$. Para $p=23$, $2^{23}-1=8\,388\,607=47\cdot178\,481$. Assim, de uma só vez, infinitos números de Mersenne ficam descartados, se houver infinitos primos de Sophie Germain dessa forma.

A criptografia

Quando você abre um site seguro, o seu computador e o servidor precisam combinar uma chave secreta através de uma rede que qualquer um pode escutar. Um dos métodos mais usados para isso, criado por Whitfield Diffie e Martin Hellman em 1976, faz contas módulo um primo $q$ enorme, com centenas de algarismos.

A segurança depende de que certo problema, o logaritmo discreto, seja difícil módulo $q$. Ele fica fácil quando $q-1$ se quebra em fatores pequenos. Por isso os padrões recomendam um primo seguro, $q=2p+1$, com $p$ também primo: aí $q-1=2p$ tem um fator primo gigante, e esse atalho fecha. O primo que Sophie Germain usava como auxiliar para estudar Fermat virou um cadeado.

Exercício: verifique que 2p + 1 divide 2ᵖ − 1 para p = 3, mas não para p = 5

Para $p=3$, que é $\equiv3\pmod4$: $2p+1=7$ e $2^3-1=7$. Divide. Para $p=5$, que é $\equiv1\pmod4$: $2p+1=11$ e $2^5-1=31$, que não é múltiplo de 11. O teorema só vale para $p\equiv3\pmod4$; para $p\equiv1\pmod4$, o que acontece é que $2p+1$ divide $2^p+1$: $2^5+1=33=3\cdot11$.

Exercício: continue a cadeia de Cunningham que começa em 41

$41\to83\to167\to335$. Os três primeiros são primos, mas $335=5\cdot67$ não é. A cadeia tem comprimento 3.

Fontes: biografia de Sophie Germain, MacTutor · Whitfield Diffie e Martin Hellman, “New Directions in Cryptography” (1976) · RFC 7919, grupos Diffie-Hellman de campo finito.

Todos os tópicos de Sophie Germain · ← O teorema de Sophie Germain e o último teorema de Fermat · A identidade de Sophie Germain: fatorar o que parece primo →

Créditos das imagens.