Algoritmo de Shor para ECDLP — Submissão ao Q-Day Prize

Solucionador quântico para o Problema do Logaritmo Discreto em Curvas Elípticas (ECDLP), desenvolvido para o Q-Day Prize Challenge pela Project Eleven. O objetivo: recuperar chaves privadas ECC em hardware quântico real usando o algoritmo de Shor.

• Autor: Giancarlo Lelli
• Contato: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• Histórico: Líder de tecnologia com mais de 10 anos em software empresarial, arquitetura full-stack e desenvolvimento cloud-native. Formação em ciência da computação com experiência prática em ecossistemas .NET, Python, Rust e Cloud. Atualmente trabalhando como Especialista Cloud GTM focado em arquitetura de soluções e engenharia de vendas.

Abordagem

Todas as curvas do desafio usam y^2 = x^3 + 7 sobre F_p (a = 0, b = 7), coincidindo com a família secp256k1. O solucionador implementa a variante de dois registros do algoritmo de Shor para ECDLP:

1. Preparar os registros de contagem |j>, |k> em superposição uniforme (Hadamard)
2. Calcular |j>|k>|jG + kQ> via 2t adições de pontos controladas (t = num_counting qubits)
3. Medir o registro do ponto, colapsando-o em algum elemento de grupo R
4. Aplicar a QFT inversa nos registros de contagem
5. Medir j, k e extrair d da relação j + kd = r (mod n)

A chave privada d é recuperada coletando múltiplas amostras (j, k) que satisfazem a mesma relação linear módulo a ordem do grupo n. O solucionador suporta seis estratégias de oráculo para as adições de pontos controladas, selecionadas automaticamente com base no tamanho da curva ou manualmente via --oracle.

Estratégias de Oráculo

Estratégia 1: Unitário Denso (padrão para n_bits <= 6)

Usada para curvas com ordem de grupo de até ~6 bits. Implementada em projecteleven.py.

Cada adição de ponto controlada "add S" é representada como uma matriz de permutação 2^(n+1) x 2^(n+1) aplicada via qc.unitary(). A matriz codifica a ação completa do grupo: o bloco superior esquerdo é a identidade (controle=0), o bloco inferior direito permuta os estados base de acordo com o mapa P -> P+S (controle=1).

• Codificação: Índice do grupo (0..n-1)
• Memória: O(2^{2n}) por matriz
• Qubits: 2t + n (dois registros de contagem + registro de ponto)
• Limitação: A decomposição unitária do Qiskit é O(4^n), tornando isso inviável além de ~6 bits

Estratégia 2: Decomposição Eficiente de Permutações (padrão para n_bits > 6)

Usada para curvas maiores. Implementada em quantum_arithmetic.py.

Em vez de construir matrizes densas, cada permutação "add S" é decomposta em transposições a partir de sua estrutura de ciclos. Cada transposição (troca de dois estados base |a> <-> |b>) é implementada com:

1. Redução CNOT -- CNOTs de um bit pivô para todos os outros bits diferentes, reduzindo a diferença de múltiplos bits a uma diferença de um único bit
2. X multicontrolado -- Uma porta MCX no bit pivô, condicionada a todos os outros bits corresponderem ao padrão alvo
3. Desfazer CNOTs -- Passo reverso 1 para restaurar os bits não pivô

O MCX usa decomposição em cadeia-V com (n-2) qubits ancilla dedicados, resultando em portas Toffoli O(n) por MCX em vez de O(n^2) sem ancillas. Cada adição controlada é construída como um subcircuito isolado e anexada como uma única porta opaca, evitando o crescimento quadrático do DAG no Qiskit.

• Codificação: Índice do grupo (0..n-1)
• Memória: O(N) por adição (N = ordem do grupo)
• Qubits: 2t + n + (n-2) ancillas
• Portas por adição: O(N * n)

Estratégia 3: Oráculo Quântico Baseado em Coordenadas (--oracle coordinate)

Disponível para curvas de até ~6 bits. Implementada em quantum_oracle.py.

Em vez de codificar pontos como índices de grupo, o registro quântico mantém as coordenadas reais (x, y) dos elementos de campo em binário mais uma flag de identidade. O layout do registro de ponto é:

• x_reg: f_bits qubits (f_bits = ceil(log2(p)))
• y_reg: f_bits qubits
• id_flag: 1 qubit (1 = ponto no infinito)

Cada "add S" controlada é computada a partir da fórmula de adição de curvas elípticas sobre todas as codificações de coordenadas válidas, produzindo uma permutação no registro de coordenadas. Essa permutação é decomposta em transposições usando a mesma infraestrutura de redução CNOT + MCX da Estratégia 2.

• Codificação: Coordenadas (x, y, id_flag)
• Qubits: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) ancillas
• Portas por adição: O(N * f_bits)

Estratégia 4: Oráculo Aritmético (--oracle arithmetic)

Estrutura para adição de pontos com escalonamento polinomial. Implementada em quantum_oracle.py e quantum_arithmetic.py.

Usa codificação por coordenadas (mesmo da Estratégia 3) com primitivas de aritmética modular baseadas em QFT como blocos de construção para uma adição de pontos totalmente aritmética. O código inclui implementações testadas de:

• Somador modular de Beauregard -- baseado em QFT (alvo + constante) mod p com descomputação adequada de ancilla
• Multiplicação modular quântico-quântico -- |a>|b>|0> -> |a>|b>|a*b mod p> via shift-and-add com duplicação modular explícita, portas O(n^3)
• Permutação de inversão modular -- |x> -> |x^{-1} mod p> via transposições de tabela de consulta
• Adição modular quântico-quântico controlada -- |a> controlado -> |a + b mod p> com redução de Beauregard

As primitivas aritméticas alcançam escalonamento O(n^3) por adição de ponto versus O(N*n) para a abordagem de permutação. No entanto, as operações baseadas em QFT carregam um fator constante ~150x maior, tornando a abordagem aritmética mais eficiente apenas para curvas acima de ~20 bits de ordem de grupo. Para os tamanhos atuais de desafio (até 12 bits), o somador baseado em permutação permanece mais rápido e é usado por padrão.

Estratégia 5: Estimação de Fase Semiclássica do Google (--oracle google)

Implementada em google_semiclassical.py. Inspirada na técnica de estimação de fase com reciclagem de qubits de Griffiths & Niu (1996), aplicada em escala por Babbush et al. (2026) para estimativas de recursos do ECDLP secp256k1. O artigo de Babbush et al. foi publicado em 30 de março de 2026.

Substitui os dois registros de contagem multi-qubit (j, k) e a QFT inversa em massa por dois qubits reciclados únicos e correções de fase condicionadas classicamente. Cada bit do registro de contagem é processado sequencialmente: preparar em |+>, aplicar adição de ponto controlada, corrigir a fase com base em todos os bits previamente medidos e então medir. Os primitivos de circuitos dinâmicos reset + if_test no Qiskit permitem isso no hardware IBM Quantum.

O oráculo para adições de pontos controladas é delegado à infraestrutura existente (unitário denso para <= 6 bits, permutação eficiente para > 6 bits), portanto a economia de qubits vem inteiramente da eliminação dos registros de contagem.

• Codificação: Mesma da estratégia subjacente (índice de grupo)
• Qubits: 2 + n_bits + ancillas (vs 2t + n_bits + ancillas)
• Compensação: Requer circuitos dinâmicos (medição no meio do circuito, reset, portas condicionadas classicamente). Funciona no IBM Heron r2 até 7 bits; a partir de 8 bits, o overhead de sincronização do feedback clássico excede o orçamento de tempo da QPU

Estratégia 6: Adição Modular Ripple-Carry (--oracle ripple)

Implementada em ripple_carry_shor.py. Usa somadores ripple-carry CDKM (Cuccaro et al. 2004) para as adições de pontos controladas, substituindo tanto as matrizes unitárias densas quanto os circuitos de transposição decompostos em ciclos.

Na codificação por índice de grupo, o ponto P = kG é representado por seu índice k no grupo cíclico. Adicionar S = sG torna-se adição modular da constante clássica s (mod n). A ideia central: cada adição de ponto controlada reduz-se a uma única adição modular controlada de uma constante conhecida, implementada via CDKMRippleCarryAdder e IntegerComparator do Qiskit.

O oráculo consiste em 2m adições modulares controladas (m por registro de contagem), onde cada adição modular controlada realiza:

1. Carregar constante no registro ancilla via CX a partir do qubit de controle
2. Meio-somador CDKM para adicionar ancilla ao acumulador (apenas portas de vizinhança imediata)
3. Comparador inteiro para detectar estouro (acc >= n)
4. Subtração condicional de n via adição controlada por flag de 2^m1 - n
5. Descomputação da flag via sondagem baseada em carry

Nenhum conhecimento da chave privada d é usado na construção do circuito. Os índices de grupo para potências de G são calculados como 2^i mod n (públicos). Os índices de grupo para potências de Q são derivados da enumeração pública do grupo cíclico gerado por G — o ponto Q é procurado nesta enumeração.

• Codificação: Índice do grupo (0..n-1)
• Qubits: 4m + 5 onde m = ceil(log2(n))
• Portas por adição: Operações CDKM O(m), cada uma com portas CX O(m)
• Escalonamento total de CX: O(m^3)
• Mapeamento em hardware: CDKM usa apenas portas de vizinhança imediata, resultando em ~1x de overhead de roteamento na topologia heavy-hex da IBM (vs 26-33x para somadores baseados em QFT)

Comparação

Primitivas Aritméticas QFT

O código inclui blocos de construção de aritmética modular baseados em QFT (somadores de Beauregard/Draper, multiplicação modular quântico-quântico, inversão/negação modulares) como base para uma codificação por coordenadas totalmente aritmética em 256 bits. Essas primitivas foram verificadas como corretas via simulação Statevector para primos até p=13.

Resultados

Chaves privadas recuperadas com sucesso em hardware IBM Quantum para curvas de desafio de até 17 bits:

Todas as execuções foram realizadas no plano de instância aberta da IBM Quantum, que concede 10 minutos de computação quântica gratuita por mês. Os logs completos de execução estão na pasta executions/.

A estratégia ripple-carry (Estratégia 6) permitiu um salto significativo: de 10 bits (40 qubits, 2M portas) para 17 bits (69 qubits, 112K portas) — um aumento de 7 bits no tamanho da chave com uma redução de 18x no número de portas de dois qubits. A estrutura de portas de vizinhança imediata do somador CDKM mapeia-se eficientemente para a topologia heavy-hex da IBM, mantendo o overhead de roteamento próximo a 1x.

Estimação de Fase Semiclássica: Circuitos Dinâmicos no Hardware IBM

A estratégia semiclássica (--oracle google) recuperou chaves com sucesso em 4, 6 e 7 bits usando circuitos dinâmicos (reset no meio do circuito, portas p condicionadas classicamente via if_test) em processadores IBM Heron r2. Em 7 bits, o circuito usa apenas 14 qubits (vs 26 para a abordagem de permutação padrão) enquanto produz contagens de portas 2Q comparáveis após a transpilação.

Em 8 bits e acima, a abordagem semiclássica torna-se impraticável no hardware IBM atual. Embora if_else e reset sejam suportados no Heron r2 (confirmado via inspeção do alvo do backend), cada ponto de feedback clássico requer uma sincronização completa da QPU — todos os 156 qubits físicos devem ficar ociosos enquanto o controlador clássico processa a condicional para os ~16 qubits ativos. Com ~295K portas CZ divididas em 16+ pontos de feedback, o overhead de execução por shot faz com que os jobs excedam o orçamento de tempo da QPU. A abordagem de permutação padrão, que executa a mesma contagem de portas em um único lote contínuo sem circuitos dinâmicos, completa-se com sucesso nessa escala.

Uma truncagem aproximada da QFT (parâmetro max_corrections) reduz o número de blocos if_else de O(n^2) para O(n), retendo apenas as k correções de fase mais próximas por etapa de medição (ângulos além de k contribuem com < pi/2^{k+1}, abaixo do piso de ruído do hardware). Com max_corrections=1, o circuito de 8 bits tem 16 blocos if_else — ainda suficiente para causar timeout no hardware IBM nessa contagem de portas.

Análise de Ruído e Fidelidade

Fidelidade Estimada do Circuito

Assumindo uma fidelidade típica de porta de dois qubits (CX) da IBM Quantum de ~99,5%, a fidelidade estimada do circuito decai exponencialmente com a contagem de portas:

A fidelidade do circuito é calculada como F ≈ (0,995)^{CX_count}. Para tudo além de 4 bits, a fidelidade estimada é astronomicamente pequena — a distribuição de saída é esmagadoramente ruído.

Por Que Ainda Funciona

Para 8 bits e acima, cada shot produz uma sequência de bits quase única (8.128 resultados únicos em 8.192 shots em 8 bits; todos os 20.000 únicos em 16 e 17 bits). A saída é indistinguível de amostragem aleatória uniforme no nível da sequência de bits. No entanto, o algoritmo ainda recupera a chave privada correta.

A principal percepção é que o pós-processamento de Shor é robusto ao ruído de uma forma que a análise bruta de sequências de bits não é. Cada shot produz um tripleto de medição (j, k, r). A extração calcula d_cand = (r - j) · k^{-1} mod n e verifica via d_cand · G == Q. Apenas o verdadeiro d passa na verificação EC, portanto mesmo um único candidato correto entre milhares de shots ruidosos é suficiente.

Um tripleto (j, k, r) puramente aleatório produz o d_cand correto com probabilidade ~1/n. Com S shots, o número esperado de acertos verificados provenientes apenas de ruído é ~S/n. Em 17 bits (n=65.173, S=20.000), isso dá ~0,3 acertos de ruído esperados — qualquer recuperação bem-sucedida nessa escala fornece evidência de sinal quântico além do piso de ruído clássico.

Para curvas menores onde shots >> n (ex.: 10 bits com n=547 e 1.024 shots), o piso de ruído é ~1.024/547 ≈ 1,9 votos por candidato. Mesmo um punhado de shots portadores de sinal empurra o d correto acima do piso de ruído. Isso explica como o algoritmo é bem-sucedido apesar de fidelidades de circuito que pareceriam tornar o cálculo impossível.

Sinal Quântico vs Ruído Clássico

Em escala de brinquedo, a etapa de verificação da extração (d_cand * G == Q) atua como um filtro que aceita apenas o verdadeiro d. Isso significa que mesmo tripletos (j, k, r) puramente aleatórios produzirão candidatos válidos a uma taxa de aproximadamente shots / n por execução. Quando shots >> n, o ruído aleatório sozinho pode recuperar d com alta probabilidade.

Para testar se o circuito quântico contribui com sinal além desse piso de ruído clássico, executamos o desafio de 6 bits (n=31) com apenas 8 shots (bem abaixo da ordem do grupo) 10 vezes no ibm_kingston:

Resultado: 4/10 sucessos (40%) vs uma linha de base de ruído clássico de ~20% (calculada via simulação de Monte Carlo: 8 sequências de bits aleatórias com (r-j)*k_inv mod 31 filtradas por verificação). Teste binomial unilateral: P(X >= 4 | n=10, p=0,20) = 0,121, indicando uma melhoria de 2x sobre o piso de ruído. Embora não seja individualmente significativo em p < 0,05 (o que exigiria 5+ sucessos), a taxa observada é consistente com um sinal quântico contribuindo com aproximadamente 1-2 pares (j, k) válidos adicionais por execução além do que o acaso fornece.

Este resultado situa-se entre o piso de ruído clássico e o regime teórico de vantagem quântica. Em tamanhos de curva maiores, onde n >> shots, a linha de base de ruído cai abaixo de 1% e qualquer recuperação bem-sucedida de chave torna-se forte evidência de computação quântica.

Início Rápido```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### Como executar

Você precisa de uma conta [IBM Quantum](https://quantum.ibm.com/). Passe seu token de API na primeira execução e ele será salvo localmente:```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

Opções de Linha de Comando

Estrutura do Projeto```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## Referências

- P. Shor, ["Algorithms for Quantum Computation: Discrete Logarithms and Factoring"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["Circuit for Shor's algorithm using 2n+3 qubits"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["A new quantum ripple-carry addition circuit"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["Quantum resource estimates for computing elliptic curve discrete logarithms"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["Semiclassical Fourier Transform for Quantum Computation"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush et al., ["Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## Licença

Este projeto é uma submissão ao Q-Day Prize Challenge lançado sob [LICENÇA MIT](https://github.com/giancarlolelli/quantum/blob/HEAD/LICENSE)