0Pricing
Cryptology Academy · Aula

GCD, função totiente de Euler e introdução à teoria dos números

Aplique GCD e a função totiente de Euler a problemas reais de criptografia

GCD, função totiente de Euler e introdução à teoria dos números é uma aula grátis de Cryptology Academy no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Cryptology Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Cryptology Academy inclui 4 aulas no total.

Boas-vindas

O GCD e a função totiente de Euler são ferramentas essenciais no RSA e em muitos outros sistemas de chave pública. Vamos aprendê-los com exemplos.

Máximo Divisor Comum (GCD)

GCD(a, b) é o maior inteiro que divide a e b sem deixar resto. GCD(12, 8) = 4. Se GCD(a, m) = 1, dizemos que a e m são coprimos ou primos entre si.

Algoritmo Euclidiano

GCD(a, b) = GCD(b, a mod b), com caso base GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Algoritmo Euclidiano estendido

A versão estendida encontra inteiros x e y tais que ax + by = GCD(a,b). Quando GCD(a,m)=1, x é o inverso modular de a módulo m. É assim que o RSA calcula as chaves privadas.

Função totiente de Euler φ(n)

φ(n) conta os inteiros de 1 a n que são coprimos com n. φ(10) = 4 porque {1, 3, 7, 9} são coprimos com 10. φ(p) = p-1 para qualquer primo p.

Totiente de um produto

Para o RSA: n = p×q (p e q primos). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Exemplo: p=5, q=11: φ(55) = 4×10 = 40. É por isso que fatorar n compromete o RSA — isso revela φ(n).

Teorema de Euler

Se GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). Essa é a base matemática da decifragem do RSA: M = C^d mod n porque e×d ≡ 1 (mod φ(n)).

Calculando d no RSA

Escolha e = 65537 (expoente público comum do RSA). Calcule d = e^(-1) mod φ(n) usando o algoritmo Euclidiano estendido. Verifique se e×d mod φ(n) == 1.

Totiente em Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Função lambda de Carmichael

O RSA moderno usa a função lambda de Carmichael λ(n) = lcm(p-1, q-1) em vez de φ(n). Ela fornece um módulo equivalente menor. PKCS#1 v2 e NIST recomendam λ(n).

Resumo da aplicação prática

GCD: verifica se e é coprimo com φ(n). Euclidiano estendido: calcula a chave privada d. Totiente: determina o grupo de expoentes para a exponenciação modular. Os três são usados em toda geração de chaves RSA.

Verificação rápida

Para um RSA com p=7 e q=11, qual é o valor de φ(n)?

Recapitulação

Excelente! GCD, o algoritmo Euclidiano e o totiente de Euler agora fazem parte das suas ferramentas. A seguir, estudaremos XOR e operações bit a bit — os blocos básicos das cifras simétricas.

Perguntas Frequentes

A aula “GCD, função totiente de Euler e introdução à teoria dos números” é grátis?

Sim — o texto completo de “GCD, função totiente de Euler e introdução à teoria dos números” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Cryptology Academy, atualize para CoddyKit PRO. O curso de Cryptology Academy inclui 4 aulas no total.

O que vou aprender em “GCD, função totiente de Euler e introdução à teoria dos números”?

Aplique GCD e a função totiente de Euler a problemas reais de criptografia Você pratica Cryptology Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Cryptology Academy?

Nenhuma experiência prévia é necessária. Cryptology Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.

Quanto tempo leva a aula “GCD, função totiente de Euler e introdução à teoria dos números”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Cryptology Academy?

Sim. Cada aula de Cryptology Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Fundamentos de binário e hexadecimal
  2. Fundamentos da aritmética modular
  3. Números primos e fatoração
  4. GCD, função totiente de Euler e introdução à teoria dos números
← Voltar para Cryptology Academy