Não costumo publicar aqui sobre computação quântica, mas faz parte do estudo! Então bora lá!
Shor’s Algorithm na Prática: Como Quebrar RSA na Era Quântica
O Algoritmo de Shor não é mais apenas teoria — é uma ameaça matemática real para qualquer algoritmo baseado na dificuldade de fatoração de inteiros ou logaritmos discretos, como RSA, ECC e DH.
Passo a Passo de Como o Shor’s Algorithm Quebra RSA
Vamos entender matematicamente como o algoritmo funciona:
1️⃣ Problema de Fatoração no RSA
O RSA é baseado em:
- N = p ⋅ q → Produto de dois números primos grandes.
- A segurança reside no fato de que, dado N, encontrar p e q é extremamente difícil.
Exemplo clássico:
N=15 → Fatores: 333 e 555
Agora, tente fazer isso com:
N=30917491529933431 (um número de 50 bits)
Ou na prática do RSA:
N de 2048 bits.
Computadores clássicos levariam milhões de anos. O Shor’s Algorithm resolve isso em tempo polinomial.
2️⃣ Fluxo Matemático do Shor
Entrada: Um inteiro NN para fatoração.
Etapas principais:
- Escolher um inteiro aleatório aa, tal que 1 < a < N. – Verificar se gcd(a,N)≠1. Se sim, já achamos um divisor.
- Executar a busca de período (Quantum Period Finding) da função:
→ Achar o menor inteiro r tal que:
- São fatores não triviais de N.
- Caso contrário, repete-se o processo.
Onde Está a Parte Quântica?
O passo 2 — encontrar o período r — é onde o computador quântico brilha. Esse problema é classicamente exponencial, mas na computação quântica é resolvido via:
- Transformada de Fourier Quântica (QFT)
- Superposição de estados
- Colapso da função de onda ao medir o período
Mão na Massa — Testando Shor na Prática
Embora computadores quânticos ainda não quebrem RSA-2048, é possível experimentar na prática usando simuladores quânticos.
Ferramentas Disponíveis
Exemplo Prático — Fatorar 15 com Qiskit
from qiskit import Aer, transpile, assemble, execute
from qiskit.algorithms import Shor
from qiskit.utils import QuantumInstance
# Cria o algoritmo de Shor para fatorar o número 15
shor = Shor()
# Configura backend (simulador quântico)
backend = Aer.get_backend('aer_simulator')
# Executa o algoritmo
result = shor.factor(N=15, quantum_instance=QuantumInstance(backend))
print("Fatores encontrados:", result.factors) Saída esperada:
Fatores encontrados: [[3, 5]] Fatoração de 21, 35 e 55 também é possível em simuladores.
Se você modificar o valor de N:
- Para N=21: Saída típica [[3, 7]]
- Para N=35: Saída típica [[5, 7]]
- Para N>100: Pode falhar ou exigir recursos computacionais intensivos no simulador.
Limitações Atuais
- Quebra de RSA real (2048 bits) requer:
- O maior feito até 2024 foi fatorar RSA-48 bits, apenas experimental.
Atualizações Técnicas (2025)
- Pesquisadores da Tsinghua University publicaram um paper reduzindo a quantidade de qubits teóricos necessários, usando algoritmos híbridos (quântico + clássico).
- IBM anunciou o plano de entregar computadores quânticos com 100.000 qubits físicos até 2029.
- O NIST já finalizou a seleção de algoritmos resistentes à computação quântica:
Quer Testar Mais na Prática?
Passos para rodar na sua máquina (com simulação):
- Instale o Qiskit:
pip install qiskit - Crie seu notebook Python.
- Use o exemplo acima ou tente:
- Acompanhe a execução do circuito quântico.
Visualize o circuito:
circuit = shor.construct_circuit(N=15)
circuit.draw('mpl') Conclusão Técnica
- O Shor’s Algorithm é comprovadamente eficiente e prático do ponto de vista matemático.
- A computação quântica ainda não está madura para quebrar RSA-2048 hoje, mas o caminho matemático e tecnológico já está traçado.
- A transição para criptografia pós-quântica não é opcional, é obrigatória para qualquer empresa que queira manter segurança digital até 2030.
