Teoria dos Números e Aritmética Modular: Da Divisibilidade à Criptografia RSA

Teoria dos números e aritmética modular

Olhe para o relógio na parede do seu escritório. Se agora são 10 horas da manhã e uma reunião longa vai durar 5 horas, você não diz que ela terminará às 15 horas no mostrador de doze horas: você diz que ela acabará às 3 horas da tarde. O que a sua mente fez de forma automática foi somar 10 com 5 (15) e subtrair o ciclo completo de 12, obtendo o resto 3. Você acabou de calcular uma congruência na aritmética modular sem precisar de nenhuma equação na lousa.

A teoria dos números costumava ser chamada pelo grande matemático G. H. Hardy de “o ramo mais puro e inútil da matemática”, uma área de contemplação estética sem aplicações no mundo prático. A invenção do computador moderno e da Internet transformou essa afirmação em pó. Hoje, a teoria dos números e a aritmética modular são o motor por trás de toda chave SSH que você usa, todo certificado HTTPS que protege transações bancárias, toda tabela hash que roda em memória e toda estrutura de fila circular em sistemas de alta performance.

Esta aula ensina os alicerces da teoria dos números aplicados à computação. Começaremos com a intuição da aritmética do relógio e o comportamento de inteiros em hardware (seções 1 a 3), avançaremos para a divisibilidade, números primos e o Algoritmo de Euclides implementado em Go (seções 4 e 5), exploraremos o Pequeno Teorema de Fermat e o funcionamento do algoritmo RSA (seções 6 e 7), e fecharemos com armadilhas de overflow, exercícios práticos, glossário e referências.

1. Aritmética modular: números em círculo

Na matemática da escola primária, a reta numérica dos números inteiros é uma estrada infinita que se estende sem limites para a esquerda e para a direita. Na arquitetura de computadores, no entanto, a memória física é finita. Os registradores de uma CPU não conseguem guardar números infinitos: um byte possui exatamente 8 bits, permitindo representar apenas 256 estados diferentes (de 0 a 255).

Quando uma variável atinge o limite superior do seu tipo de dado e sofre mais um incremento, a estrada linear se curva e forma um círculo fechado. Isso é a aritmética modular:

Dizemos que dois números inteiros a e b são congruentes módulo m (escrito como a ≡ b mod m) se a sua diferença (a - b) for um múltiplo inteiro de m. Em termos práticos de programação, isso significa que a e b produzem exatamente o mesmo resto quando divididos por m.

15 ≡ 3 (mod 12), pois 15 - 3 = 12 (múltiplo de 12). 27 ≡ 3 (mod 12), pois 27 - 3 = 24 (múltiplo de 12).

O diagrama acima ilustra como o operador módulo disciplina dados lineares em um espaço cíclico. Ao somar 5 horas ao marcador inicial de 10 horas, o valor bruto 15 entra no operador módulo 12. O cálculo extrai o ciclo completo e fixa o ponteiro no estado 3.

No desenvolvimento de software, essa mecânica é o coração dos chamados buffers circulares (ring buffers). Se você tem uma fila em memória de tamanho fixo N (por exemplo, 1024 posições), você nunca precisa realocar arrays quando o cursor atinge o fim do slice: basta calcular proximo_indice = (cursor_atual + 1) % N. O ponteiro dá a volta automaticamente para a posição zero com custo computacional praticamente nulo.

2. Aritmética modular no hardware e em Go

Em linguagens como Go e C, a aritmética de inteiros sem sinal opera estritamente na aritmética modular por especificação de hardware. Quando você declara um uint8, você está trabalhando no anel modular ℤ₂₅₆.

Veja o que acontece no terminal quando incrementamos o valor máximo de um byte:

package main

import "fmt"

func main() {
	var contador uint8 = 255

	fmt.Printf("Valor antes do incremento: %d\n", contador) // 255

	// 255 + 1 matematicamente seria 256.
	// No anel modular Z_256: 256 mod 256 = 0.
	contador = contador + 1

	fmt.Printf("Valor apos o incremento (wrap-around): %d\n", contador) // 0
}

O processador não dispara um erro nem encerra a aplicação: ele simplesmente descarta o nono bit de transporte (carry bit) que não cabe no registrador, resultando no valor zero. Esse fenômeno chama-se wrap-around.

Em sistemas críticos, o desconhecimento dessa propriedade causa desastres históricos, como a falha do foguete Ariane 5 em 1996, onde a conversão de um número de 64 bits para um inteiro de 16 bits sofreu overflow e desorientou os computadores de bordo.

3. Divisibilidade e o algoritmo da divisão

Sejam a e b números inteiros, com b ≠ 0. Dizemos que b divide a (notação: b | a) se existir um inteiro k tal que a = b · k. Nesse caso, dizemos que b é divisor de a e a é múltiplo de b.

Quando a divisão não é exata, entra em cena o Teorema da Divisão Euclidiana: Para quaisquer inteiros a e b (com b > 0), existem inteiros únicos q (quociente) e r (resto) tais que: a = b · q + r, com 0 ≤ r < b.

O valor r é exatamente o que o operador % de Go devolve quando operamos com números positivos: q = a / b r = a % b

Cuidado com números negativos no código

A definição matemática exige que o resto r seja sempre positivo ou zero (0 ≤ r < b). Porém, em quase todas as linguagens de programação modernas (incluindo Go, C e Java), o operador % calcula o resto truncado em direção a zero, preservando o sinal do dividendo:

Em Go: -7 % 3 resulta em -1, e não 2 (que seria a convenção matemática clássica, já que -7 = 3 · (-3) + 2). Para obter o módulo estritamente positivo em Go, usamos a função auxiliar:

func ModuloPositivo(a, m int) int {
	return (a%m + m) % m
}

4. O Algoritmo de Euclides para o MDC

O Máximo Divisor Comum (MDC) entre dois inteiros a e b é o maior número inteiro que divide ambos simultaneamente. Se MDC(a, b) = 1, dizemos que a e b são primos entre si (coprimos).

Por volta do ano 300 antes de Cristo, Euclides de Alexandria formulou um dos primeiros algoritmos documentados da história humana. Ele percebeu uma propriedade genial: o MDC entre dois números a e b é rigorosamente o mesmo que o MDC entre b e o resto da divisão de a por b.

MDC(a, b) = MDC(b, a mod b)

Com essa regra simples, não precisamos fatorar números gigantescos para achar divisores comuns: basta repetir a operação de módulo até que o resto seja zero.

O diagrama detalha a busca pelo MDC entre 252 e 105. No primeiro passo, calculamos 252 mod 105, que deixa resto 42; o problema reduz-se a MDC(105, 42). No segundo passo, 105 mod 42 deixa resto 21; o problema reduz-se a MDC(42, 21). No terceiro passo, 42 mod 21 deixa resto zero. Atingido o caso base (b == 0), o algoritmo interrompe a recursão e entrega o número 21 como a resposta final exata.

Veja a implementação em Go, que roda em tempo logarítmico O(log(min(a, b))):

package main

import "fmt"

// MDC calcula o Maximo Divisor Comum pelo Algoritmo de Euclides.
func MDC(a, b int) int {
	// Caso base da inducao: quando o segundo operando zera, o primeiro e o MDC.
	if b == 0 {
		return a
	}
	// Passo indutivo: reduzimos o tamanho dos operandos pelo resto.
	return MDC(b, a%b)
}

func main() {
	x, y := 252, 105
	fmt.Printf("MDC(%d, %d) = %d\n", x, y, MDC(x, y)) // Saida: 21
}

5. Números primos e a moeda de ouro do hashing

Um número inteiro p > 1 é primo se os seus únicos divisores positivos forem 1 e ele próprio. Pelo Teorema Fundamental da Aritmética, todo número inteiro maior que 1 pode ser decomposto de forma única em um produto de fatores primos (como 60 = 2² · 3 · 5).

Por que engenheiros de software são obcecados por números primos na hora de criar funções hash e tabelas hash?

Suponha que você crie uma tabela hash com 10 posições (m = 10) e que os IDs gerados pelo seu sistema sejam sempre múltiplos de 2 (como 2, 4, 6, 8, 10, 12…). Ao aplicar a função hash(id) = id % 10, os restos possíveis serão exclusivamente 0, 2, 4, 6 e 8. Metade das posições da sua tabela ficará completamente vazia, enquanto as posições pares sofrerão colisões constantes.

Quando escolhemos um número primo p para o tamanho da tabela ou para os multiplicadores da função hash (como o clássico número 31 em algoritmos de string hashing), garantimos que qualquer padrão ou periodicidade nos dados de entrada tenha probabilidade mínima de compartilhar divisores com p. A distribuição dos restos pelo anel modular torna-se quase uniforme, mantendo as operações de busca em tempo médio constante O(1).

6. O Pequeno Teorema de Fermat

Em 1640, Pierre de Fermat estabeleceu uma propriedade da aritmética modular com um impacto prático imenso na segurança da computação:

Se p for um número primo e a for um número inteiro não divisível por p, então: aᵖ⁻¹ ≡ 1 (mod p)

Multiplicando ambos os lados por a, temos a forma equivalente: aᵖ ≡ a (mod p)

Esse teorema tem duas aplicações diretas no código de software:

1. Testes rápidos de primalidade

Para verificar se um número gigante n com centenas de dígitos é primo, você não precisa tentar dividi-lo por todos os números menores que a raiz quadrada dele. Você pode sortear uma base a e calcular aⁿ⁻¹ mod n. Se o resultado for diferente de 1, o teorema garante que n com certeza absoluta não é primo. Algoritmos modernos de criptografia (como Miller-Rabin) expandem esse princípio para encontrar números primos gigantescos em frações de segundo.

2. Inverso multiplicativo modular

Em números reais, o inverso de 5 é 1/5, pois 5 · (1/5) = 1. Na aritmética modular de inteiros, não existem frações. O inverso modular de a módulo p é um número inteiro x tal que a · x ≡ 1 (mod p). Pelo teorema de Fermat: a · aᵖ⁻² = aᵖ⁻¹ ≡ 1 (mod p) Logo, o inverso de a módulo p é simplesmente aᵖ⁻² mod p. Essa operação permite realizar “divisões” seguras dentro da criptografia.

7. Criptografia RSA: a função alçapão

Até os anos 1970, toda a criptografia do mundo era simétrica: quem cifrava e quem decifrava precisava compartilhar exatamente a mesma chave secreta prévia. Se Alice e Bob quisessem conversar com segurança, precisavam primeiro se encontrar fisicamente para combinar a chave. Na escala da Internet mundial com bilhões de celulares acessando servidores remotos, isso seria inviável.

Em 1977, Ron Rivest, Adi Shamir e Leonard Adleman inventaram o algoritmo RSA, baseado em um conceito da teoria dos números conhecido como função alçapão (trapdoor one-way function): uma operação que é extremamente fácil de calcular em uma direção, mas praticamente impossível de desfazer na direção oposta a menos que você possua uma informação secreta.

O diagrama detalha a engrenagem do RSA:

1. A assimetria computacional

Multiplicar dois números primos gigantes p e q (cada um com centenas de dígitos) para obter o produto n = p · q leva microssegundos na CPU de qualquer celular. No entanto, se você entregar apenas o número n para o computador mais potente do planeta e pedir para ele descobrir quais são os primos originais p e q, a máquina levará milhares de anos tentando fatorá-lo.

2. A geração do par de chaves

O servidor escolhe dois primos secretos p e q e calcula:

• Módulo público: n = p · q
• Totiente secreto de Euler: φ(n) = (p - 1)(q - 1)
• Escolhe um expoente público e (geralmente 65537) coprimo com φ(n).
• Calcula a chave privada d, que é o inverso multiplicativo de e módulo φ(n): e · d ≡ 1 mod φ(n).

O par (e, n) é publicado abertamente na Internet como a chave pública. O valor d é guardado no servidor em sigilo absoluto como a chave privada. Os primos p e q originais são destruídos da memória.

3. Cifragem e decifragem modular

Quando um navegador envia sua senha para o banco, ele transforma a mensagem de texto em um número m e calcula o texto cifrado c usando a chave pública disponível: c = mᵉ mod n

O pacote cifrado c viaja pela Internet aberta. Qualquer bisbilhoteiro pode interceptar c e sabe o valor de n e de e, mas não consegue extrair a raiz e-ésima em aritmética modular sem conhecer φ(n).

Quando o servidor do banco recebe o valor c, ele aplica o expoente secreto d da sua chave privada: cᵈ mod n = (mᵉ)ᵈ mod n = mᵉᵈ mod n

Pelo Teorema de Euler (a generalização do teorema de Fermat), mᵉᵈ ≡ m (mod n). O texto original m reaparece intacto.

8. Erros comuns e boas práticas

1. Usar o operador % ingênuo com inteiros negativos. Em Go, -15 % 10 resulta em -5. Se você usar esse valor diretamente como índice de um array (slice[resto]), o programa sofrerá um panic de index out of range em tempo de execução. Sempre normalize restos negativos com a função de módulo positivo.
2. Não proteger contra ataques de canal lateral (timing attacks). Comparar hashes ou chaves criptográficas usando operadores comuns como a == b permite que um invasor meça variações de nanossegundos no tempo de resposta da CPU e descubra a chave byte por byte. Para dados criptográficos, use sempre funções de tempo constante, como crypto/subtle.ConstantTimeCompare.
3. Tentar implementar algoritmos criptográficos do zero para produção. Escrever o RSA em vinte linhas de código com números inteiros comuns é excelente para aprender a matemática, mas mortal em sistemas reais: inteiros padrão sofrem overflow, bibliotecas não especializadas não protegem a memória RAM contra vazamentos e não aplicam o preenchimento de segurança obrigatório (como OAEP). Em código real, consuma pacotes consolidados como crypto/rsa ou crypto/ed25519.
4. Tamanhos de chave obsoletos. Na teoria dos números, a capacidade de fatoração avança com novos algoritmos matemáticos e supercomputadores. Chaves RSA de 1024 bits são consideradas inseguras hoje; o padrão atual para sistemas que ainda usam RSA exige no mínimo 2048 ou 4096 bits, embora algoritmos baseados em curvas elípticas (como ECDSA e Ed25519) venham substituindo o RSA por oferecerem chaves muito menores com a mesma segurança matemática.

9. Exercícios de fixação

Exercício 1: Exponenciação modular rápida em Go

Em algoritmos criptográficos como RSA, precisamos calcular potências astronômicas sob um módulo, como 7¹⁰⁰⁰ mod 13. Se calcularmos 7¹⁰⁰⁰ primeiro, o número terá mais de 800 dígitos e estourará qualquer registrador de computador.

A propriedade fundamental da aritmética modular permite aplicar o módulo em cada multiplicação intermediária: (a · b) mod m = [(a mod m) · (b mod m)] mod m

Implemente em Go uma função de exponenciação modular que calcule (baseᵉˣᵖ) % mod em tempo O(log exp):

package main

import "fmt"

// ModPow calcula (base^exp) % mod sem causar overflow de memoria.
func ModPow(base, exp, mod int64) int64 {
	var resultado int64 = 1
	base = base % mod

	for exp > 0 {
		// Se o expoente for impar, multiplica a base pelo acumulador
		if exp%2 == 1 {
			resultado = (resultado * base) % mod
		}
		// Dobra a potencia da base e divide o expoente por 2
		base = (base * base) % mod
		exp = exp / 2
	}

	return resultado
}

func main() {
	// Calcula 7^1000 mod 13 instantaneamente
	fmt.Printf("7^1000 mod 13 = %d\n", ModPow(7, 1000, 13)) // Saida: 9
}

Exercício 2: Resolução com o Pequeno Teorema de Fermat

Calcule manualmente o resto da divisão de 3⁵⁰ por 11 (ou seja, determine 3⁵⁰ mod 11).

Resolução:

1. Identificamos que o módulo p = 11 é um número primo e a base a = 3 não é divisível por 11.
2. Aplicamos o Pequeno Teorema de Fermat: 3¹¹⁻¹ ≡ 1 (mod 11) ⟹ 3¹⁰ ≡ 1 (mod 11).
3. Decompomos o expoente 50 como múltiplo de 10: 3⁵⁰ = (3¹⁰)⁵.
4. Substituímos a congruência na expressão: 3⁵⁰ = (3¹⁰)⁵ ≡ 1⁵ ≡ 1 (mod 11). Resposta: O resto da divisão de 3⁵⁰ por 11 é exatamente 1. Não foi necessário fazer nenhuma multiplicação de 50 fatores.

10. Glossário

• Aritmética modular: Sistema de aritmética para inteiros onde os números voltam ao início após atingirem um determinado valor fixo (o módulo).
• Congruência: Relação de equivalência que indica que dois inteiros deixam o mesmo resto quando divididos pelo mesmo módulo.
• Wrap-around: Comportamento de variáveis inteiras em registradores finitos que voltam a zero após ultrapassarem a capacidade máxima de bits.
• Máximo Divisor Comum (MDC): O maior número inteiro positivo que divide dois números sem deixar resto.
• Números coprimos: Dois inteiros cujo MDC é igual a 1 (não compartilham fatores primos).
• Função alçapão (Trapdoor function): Função fácil de computar em um sentido, mas computacionalmente inviável de inverter sem uma chave secreta auxiliar.
• Totiente de Euler φ(n): Função que conta quantos inteiros positivos menores que n são coprimos com n.

11. Fontes e referências

• Rosen, Kenneth H. Discrete Mathematics and Its Applications, 8ª edição, McGraw-Hill, 2019 (Capítulo 4: Number Theory and Cryptography).
• Cormen, Thomas H. et al. Introduction to Algorithms, 4ª edição, MIT Press, 2022 (Capítulo 31: Number-Theoretic Algorithms).
• Katz, Jonathan; Lindell, Yehuda. Introduction to Modern Cryptography, 3ª edição, CRC Press, 2020 (Capítulo 8: Public-Key Cryptography and Number Theory). Consulta em novembro de 2026.

Relacionados

• Lógica proposicional e de primeira ordem
• Indução matemática
• Teoria dos conjuntos, relações e funções
• Tecnologia/Hardware/Representação da informação/Inteiros, complemento de dois e overflow