0Pricing
Cryptology Academy · Aula

Números primos e fatoração

Aprenda por que os números primos são a base da criptografia de chave pública

Números primos e fatoração é uma aula grátis de Cryptology Academy no CoddyKit. Esta é a aula 3 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

Números primos são divisíveis apenas por 1 e por si mesmos. Eles são os átomos da multiplicação — e a base do RSA, do Diffie-Hellman e de muitos outros sistemas criptográficos.

Definição e exemplos

Primos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Um número é primo se seus únicos divisores positivos são 1 e ele mesmo. 1 não é primo por convenção: NOT.

Teorema Fundamental da Aritmética

Todo inteiro > 1 pode ser fatorado em primos de uma única forma (a menos da ordem). 60 = 2² × 3 × 5. Essa unicidade é o que torna possível a criptografia baseada em fatoração.

Divisão por tentativa

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Só é necessário verificar até √n — se nenhum fator for encontrado abaixo de √n, n é primo.

Crivo de Eratóstenes

Para encontrar todos os primos até N: comece com uma lista de números de 2 a N. Risque os múltiplos de 2, depois os de 3, depois os de 5 e assim por diante. Os números restantes são primos. O algoritmo tem complexidade O(N log log N).

Teste de primalidade: Miller-Rabin

Para números grandes (2048 bits), a divisão por tentativa é lenta demais. Miller-Rabin é um teste probabilístico: execute-o 40 vezes e a probabilidade de erro será < 4^(-40).

Fatoração de inteiros

Dado n = p × q, encontrar p e q é o problema da fatoração de inteiros. Se n tiver 2048 bits, os melhores algoritmos conhecidos exigem 2^112 operações — algo inviável atualmente.

Por que o RSA usa dois primos grandes

O módulo RSA é n = p × q. Saber n, mas não p e q, torna difícil calcular a chave privada. A segurança depende inteiramente da dificuldade de fatorar n.

Gerando primos grandes

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Oráculo: gere um número ímpar aleatório, teste-o com Miller-Rabin e repita até encontrar um primo.

Primos seguros e primos fortes

Um primo seguro é p = 2q+1, em que q também é primo. Primos seguros resistem a certos ataques contra DH. Às vezes, o RSA usa primos fortes para impedir o ataque p-1 de Pollard.

Intervalos entre primos e infinitude

Euclides provou que há infinitos primos em 300 BCE. A conjectura dos primos gêmeos (existem infinitos primos p e p+2) ainda não foi provada. Nunca ficamos sem primos para a criptografia.

Verificação rápida

Por que o RSA usa números primos grandes?

Recapitulação

Você compreende os números primos e a fatoração. A seguir, aplicaremos a função totiente de Euler e o GCD — as últimas ferramentas matemáticas necessárias antes do RSA.

Perguntas Frequentes

A aula “Números primos e fatoração” é grátis?

Sim — o texto completo de “Números primos e fatoração” é 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 “Números primos e fatoração”?

Aprenda por que os números primos são a base da criptografia de chave pública 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 3 de 4.

Quanto tempo leva a aula “Números primos e fatoração”?

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