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

Solver quântico para o Problema do Logaritmo Discreto de Curva Elíptica (ECDLP), construído para o Desafio Q-Day Prize 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 nativo em nuvem. Formação em ciência da computação com experiência prática em ecossistemas .NET, Python, Rust e Cloud. Atualmente atuando como Especialista GTM em Nuvem, 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), correspondendo à família secp256k1. O solver implementa a variante de dois registradores do algoritmo de Shor para ECDLP:

1. Preparar os registradores de contagem |j>, |k> em superposição uniforme (Hadamard)
2. Computar |j>|k>|jG + kQ> via 2t adições de pontos controladas (t = num_qubits_contagem)
3. Medir o registrador de ponto, colapsando-o para algum elemento de grupo R
4. Aplicar QFT inversa aos registradores 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 solver 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 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 é identidade (controle=0), o bloco inferior direito permuta os estados base de acordo com o mapa P -> P+S (controle=1).

• Codificação: Índice de grupo (0..n-1)
• Memória: O(2^{2n}) por matriz
• Qubits: 2t + n (dois registradores de contagem + registrador 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 ciclos convertidos em transposições. 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 multibit para 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 O(n) portas Toffoli 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 de 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 registrador quântico mantém as coordenadas reais (x, y) dos elementos de campo em binário mais um sinalizador de identidade. O layout do registrador 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 EC sobre todas as codificações de coordenadas válidas, produzindo uma permutação no registrador de coordenadas. Essa permutação é decomposta em ciclos convertidos 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 de coordenadas (mesmo da Estratégia 3) com primitivas aritméticas modulares baseadas em QFT como blocos de construção para adição de pontos totalmente aritmética. O código inclui implementações testadas de:

• Somador modular 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, O(n^3) portas
• Permutação de inverso 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 Beauregard

As primitivas aritméticas alcançam escalonamento O(n^3) por adição de ponto vs 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 do desafio (até 12 bits), o somador baseado em permutação permanece mais rápido e é usado por padrão.

Estratégia 5: Estimativa de Fase Semiclássica do Google (--oracle google)

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

Substitui os dois registradores de contagem multiqubit (j, k) e a QFT inversa em massa por dois qubits reciclados únicos e correções de fase condicionadas classicamente. Cada bit do registrador de contagem é processado sequencialmente: preparar em |+>, aplicar adição de ponto controlada, corrigir fase com base em todos os bits medidos anteriormente, então medir. Os primitivos de circuito dinâmico reset + if_test no Qiskit permitem isso em 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), então a economia de qubits vem inteiramente da eliminação dos registradores 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 em IBM Heron r2 até 7 bits; em 8 bits ou mais, a sobrecarga de sincronização de 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 matrizes unitárias densas quanto circuitos de transposição decompostos em ciclos.

Na codificação de índice de grupo, 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 percepção chave: cada adição de ponto controlada se reduz 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 registrador de contagem), onde cada adição modular controlada realiza:

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

Nenhum conhecimento da chave privada d é usado na construção do circuito. Índices de grupo para potências de G são computados como 2^i mod n (públicos). Í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 de 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 de hardware: CDKM usa apenas portas de vizinhança próxima, resultando em ~1x sobrecarga 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 aritméticos modulares baseados em QFT (somadores Beauregard/Draper, multiplicação modular quântico-quântico, inverso/negação modular) como base para codificação de coordenadas totalmente aritmética em 256 bits. Essas primitivas foram verificadas corretas via simulação Statevector para primos até p=13.

Resultados

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

Todas as execuções foram feitas no plano de instância aberta do IBM Quantum, que concede 10 minutos de computação quântica gratuita por mês. 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 na contagem de portas de dois qubits. A estrutura de portas de vizinhança próxima do somador CDKM mapeia eficientemente para a topologia heavy-hex da IBM, mantendo a sobrecarga de roteamento próxima a 1x.

Estimativa de Fase Semiclássica: Circuitos Dinâmicos em Hardware IBM

A estratégia semiclássica (--oracle google) recuperou chaves com sucesso em 4 bits, 6 bits 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 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 distribuídas em 16+ pontos de feedback, a sobrecarga 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 como um único lote contínuo sem circuitos dinâmicos, é concluída com sucesso nesta 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) ao reter 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 nesta 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) do IBM Quantum de ~99,5%, a fidelidade estimada do circuito cai 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 cadeia de bits quase única (8,128 resultados únicos em 8,192 shots em 8 bits; todos os 20,000 únicos em 16 bits e 17 bits). A saída é indistinguível de amostragem aleatória uniforme no nível da cadeia de bits. No entanto, o algoritmo ainda recupera a chave privada correta.

A percepção chave é que o pós-processamento de Shor é robusto ao ruído de uma forma que a análise bruta de cadeias de bits não é. Cada shot produz um tripleto de medição (j, k, r). A extração computa 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 apenas do 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 nesta escala fornece evidência de sinal quântico além do piso de ruído clássico.

Para curvas menores onde shots >> n (por exemplo, 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 contendo sinal empurra o d correto acima do piso de ruído. Isso explica como o algoritmo é bem-sucedido apesar de fidelidades de circuito que tornariam a computação aparentemente 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 d verdadeiro. 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 deste 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% (computada via simulação de Monte Carlo: 8 cadeias de bits aleatórias com (r-j)*k_inv mod 31 filtradas por verificação). Teste binomial unicaudal: 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 estatisticamente significativo individualmente em p < 0,05 (que exigiria 5+ sucessos), a taxa observada é consistente com um sinal quântico contribuindo com aproximadamente 1-2 pares (j, k) adicionais válidos 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 de vantagem quântica teórica. 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 da CLI

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 [MIT LICENSE](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE)