O algoritmo de Shor e o RSA
Aula 12 de 23 do curso “Quântica”. Grátis, com animações e teste.
Um cadeado de números primos
Quando você entra num site por HTTPS, assina um documento ou paga com cartão, muitas vezes o RSA está trabalhando; ele foi criado em 1977. A ideia é simples: multiplicar dois primos grandes é fácil, mas fatorar o resultado é muito difícil. 61 × 53 você calcula em um minuto, mas achar os fatores de 3233 já demora mais. O RSA-2048 usa um número de 617 dígitos, e computadores clássicos não o fatorariam nem na idade do universo.
O truque de Shor: transformar fatoração em ritmo
Em 1994 o matemático Peter Shor, do Bell Labs, percebeu que fatorar um número pode virar a busca de um ritmo. Pegue N = 15 e o número 7. Eleve 7 a potências e pegue o resto da divisão por 15: dá 1, 7, 4, 13 e de novo 1, 7, 4, 13. O ritmo se repete a cada 4 passos. Sabendo o ritmo, a aritmética da escola dá os fatores: 3 e 5. Em números pequenos o ritmo aparece a olho; em números de centenas de dígitos ele é astronomicamente longo, e aí entra o computador quântico.
Como um computador quântico ouve o ritmo
Passo um: uma superposição de todas as potências de uma vez, com um padrão repetido escondido nas amplitudes. Passo dois: a transformada quântica de Fourier, ou QFT. Ela faz o que o equalizador de um player faz: separa o sinal em frequências. Graças à interferência, a frequência certa é amplificada e as outras se anulam. Você mede e obtém um número do qual se calcula o período. Essa é a aceleração exponencial: uma tarefa de bilhões de anos vira horas ou dias.
Quantos qubits são precisos e por que o número cai
No papel, Shor quebrou o RSA há tempos, mas precisa de um grande computador com correção de erros. As estimativas caem rápido. Em 2019 Craig Gidney e Martin Ekerå calcularam cerca de 20 milhões de qubits físicos e 8 horas. Em maio de 2025 Gidney mostrou menos de um milhão de qubits e menos de uma semana. Em fevereiro de 2026 a startup Iceberg Quantum anunciou um projeto com menos de 100.000 qubits, e no fim de março uma equipe do Caltech estimou que 10.000–20.000 átomos neutros poderiam bastar. As duas estimativas supõem arquiteturas especiais que ainda não existem. Os melhores chips hoje têm milhares de qubits, e ainda falta qualidade. Mas a distância diminui dos dois lados.
Não é só o RSA que está em risco
O mesmo algoritmo de Shor também quebra curvas elípticas. Nelas se apoiam as assinaturas do Bitcoin e do Ethereum e a troca de chaves do HTTPS. Em março de 2026 uma equipe do Google com coautores como o criptógrafo Dan Boneh estimou que para a curva do Bitcoin bastam menos de 500.000 qubits físicos, e que, depois que a chave pública aparece, o ataque leva cerca de 9 minutos. Já as cifras simétricas como o AES e os hashes como o SHA-256 não sofrem com Shor: só enfrentam a “raiz” de Grover. Mais sobre cripto no último nível.
Por que a proteção tem que começar agora
Se um grande computador quântico ainda está a anos, por que a pressa? Por causa da tática “colete agora, decifre depois”. Um atacante pode gravar hoje o tráfego cifrado e guardá-lo até o dia em que conseguir quebrá-lo. Dados médicos, segredos de Estado e conversas precisam continuar secretos por décadas. Por isso, em 2024 o NIST aprovou os primeiros padrões pós-quânticos, e Signal, iMessage e Chrome já ativaram essa proteção para usuários comuns.
Teste-se
- O que torna o RSA vulnerável a um computador quântico?
Resposta certa: Fatorar vira achar um período, e a QFT acha períodos bem. Shor transforma a fatoração em achar um ritmo, e a QFT o extrai com interferência. Daí a aceleração exponencial. - Por que proteger dados agora se o Q-Day está a anos?
Resposta certa: O tráfego pode ser gravado agora e decifrado depois. A tática “colete agora, decifre depois” torna a ameaça real hoje para dados de vida longa. - Qual destes o Shor não quebra?
Resposta certa: AES-256. O AES é uma cifra simétrica sem “ritmo” para Shor. Só o Grover atua contra ele, e a chave de 256 bits aguenta.