Algoritmo de Shor para ECDLP — Envío para el Q-Day Prize

Solucionador cuántico para el Problema del Logaritmo Discreto de Curva Elíptica (ECDLP), construido para el Q-Day Prize Challenge por Project Eleven. El objetivo: recuperar claves privadas ECC en hardware cuántico real usando el algoritmo de Shor.

• Autor: Giancarlo Lelli
• Contacto: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• Antecedentes: Líder tecnológico con más de 10 años en software empresarial, arquitectura full-stack y desarrollo nativo en la nube. Formación en ciencias de la computación con experiencia práctica en los ecosistemas .NET, Python, Rust y Cloud. Actualmente trabaja como Especialista GTM en la nube, centrado en arquitectura de soluciones e ingeniería de ventas.

Enfoque

Todas las curvas del desafío usan y^2 = x^3 + 7 sobre F_p (a = 0, b = 7), coincidiendo con la familia secp256k1. El solucionador implementa la variante de dos registros del algoritmo de Shor para ECDLP:

1. Preparar los registros de conteo |j>, |k> en superposición uniforme (Hadamard)
2. Calcular |j>|k>|jG + kQ> mediante 2t sumas de puntos controladas (t = qubits de conteo)
3. Medir el registro del punto, colapsándolo a algún elemento de grupo R
4. Aplicar QFT inverso a los registros de conteo
5. Medir j, k y extraer d de la relación j + kd = r (mod n)

La clave privada d se recupera recolectando múltiples muestras (j, k) que satisfacen la misma relación lineal módulo el orden del grupo n. El solucionador admite seis estrategias de oráculo para las sumas de puntos controladas, seleccionadas automáticamente según el tamaño de la curva o manualmente mediante --oracle.

Estrategias de Oráculo

Estrategia 1: Unitaria Densa (predeterminada para n_bits <= 6)

Usada para curvas con orden de grupo hasta ~6 bits. Implementada en projecteleven.py.

Cada suma de puntos controlada "añadir S" se representa como una matriz de permutación de 2^(n+1) x 2^(n+1) aplicada mediante qc.unitary(). La matriz codifica la acción completa del grupo: el bloque superior izquierdo es identidad (control=0), el bloque inferior derecho permuta los estados base según el mapa P -> P+S (control=1).

• Codificación: Índice de grupo (0..n-1)
• Memoria: O(2^{2n}) por matriz
• Qubits: 2t + n (dos registros de conteo + registro del punto)
• Limitación: La descomposición unitaria de Qiskit es O(4^n), lo que la hace inviable más allá de ~6 bits

Estrategia 2: Descomposición Eficiente de Permutaciones (predeterminada para n_bits > 6)

Usada para curvas más grandes. Implementada en quantum_arithmetic.py.

En lugar de construir matrices densas, cada permutación "añadir S" se descompone en ciclos como transposiciones. Cada transposición (intercambio de dos estados base |a> <-> |b>) se implementa con:

1. Reducción CNOT -- CNOTs desde un bit pivote a todos los otros bits que difieren, reduciendo la diferencia de múltiples bits a una diferencia de un solo bit
2. X multicontrolada -- Una puerta MCX sobre el bit pivote, condicionada a que todos los otros bits coincidan con el patrón objetivo
3. Deshacer CNOTs -- Invertir el paso 1 para restaurar los bits no pivote

La MCX usa descomposición en cadena-V con (n-2) qubits ancilla dedicados, dando O(n) puertas Toffoli por MCX en lugar de O(n^2) sin ancillas. Cada suma controlada se construye como un subcircuito aislado y se añade como una única puerta opaca, evitando el crecimiento cuadrático del DAG en Qiskit.

• Codificación: Índice de grupo (0..n-1)
• Memoria: O(N) por suma (N = orden del grupo)
• Qubits: 2t + n + (n-2) ancillas
• Puertas por suma: O(N * n)

Estrategia 3: Oráculo Cuántico Basado en Coordenadas (--oracle coordinate)

Disponible para curvas de hasta ~6 bits. Implementada en quantum_oracle.py.

En lugar de codificar puntos como índices de grupo, el registro cuántico contiene las coordenadas (x, y) de elementos de campo en binario más un indicador de identidad. La disposición del registro del punto es:

• x_reg: f_bits qubits (f_bits = ceil(log2(p)))
• y_reg: f_bits qubits
• id_flag: 1 qubit (1 = punto en el infinito)

Cada suma controlada "añadir S" se calcula a partir de la fórmula de suma de EC sobre todas las codificaciones de coordenadas válidas, produciendo una permutación en el registro de coordenadas. Esta permutación se descompone en ciclos como transposiciones usando la misma infraestructura de reducción CNOT + MCX que la Estrategia 2.

• Codificación: Coordenadas (x, y, id_flag)
• Qubits: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) ancillas
• Puertas por suma: O(N * f_bits)

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

Marco para suma de puntos con escalado polinómico. Implementada en quantum_oracle.py y quantum_arithmetic.py.

Usa codificación de coordenadas (igual que la Estrategia 3) con primitivas aritméticas modulares basadas en QFT como componentes para la suma de puntos completamente aritmética. El código incluye implementaciones probadas de:

• Sumador modular de Beauregard -- basado en QFT (objetivo + constante) mod p con descomputación de ancilla adecuada
• Multiplicación modular cuántico-cuántico -- |a>|b>|0> -> |a>|b>|a*b mod p> mediante desplazar-y-sumar con duplicación modular explícita, O(n^3) puertas
• Permutación inversa modular -- |x> -> |x^{-1} mod p> mediante transposiciones de tabla de búsqueda
• Suma modular cuántico-cuántico controlada -- |a> controlado -> |a + b mod p> con reducción de Beauregard

Las primitivas aritméticas logran un escalado O(n^3) por suma de puntos frente a O(N*n) para el enfoque de permutación. Sin embargo, las operaciones basadas en QFT tienen un factor constante ~150 veces mayor, lo que hace que el enfoque aritmético sea más eficiente solo para curvas con orden de grupo superior a ~20 bits. Para los tamaños de desafío actuales (hasta 12 bits), el sumador basado en permutaciones sigue siendo más rápido y se usa por defecto.

Estrategia 5: Estimación de Fase Semiclásica de Google (--oracle google)

Implementada en google_semiclassical.py. Inspirada en la técnica de estimación de fase con reciclaje de qubits de Griffiths & Niu (1996), aplicada a escala en Babbush et al. (2026) para estimaciones de recursos ECDLP en secp256k1. El artículo de Babbush et al. se publicó el 30 de marzo de 2026.

Reemplaza los dos registros de conteo multiqubit (j, k) y el QFT inverso masivo con dos qubits reciclados individuales y correcciones de fase condicionadas clásicamente. Cada bit del registro de conteo se procesa secuencialmente: preparar en |+>, aplicar suma de puntos controlada, corregir fase basándose en todos los bits medidos previamente, luego medir. Las primitivas de circuito dinámico reset e if_test en Qiskit permiten esto en hardware IBM Quantum.

El oráculo para sumas de puntos controladas se delega en la infraestructura existente (unitaria densa para <= 6 bits, permutación eficiente para > 6 bits), por lo que el ahorro de qubits proviene únicamente de eliminar los registros de conteo.

• Codificación: Igual que la estrategia subyacente (índice de grupo)
• Qubits: 2 + n_bits + ancillas (frente a 2t + n_bits + ancillas)
• Compromiso: Requiere circuitos dinámicos (medición en medio del circuito, reset, puertas condicionadas clásicamente). Funciona en IBM Heron r2 hasta 7 bits; a partir de 8 bits, la sobrecarga de sincronización de realimentación clásica supera el presupuesto de tiempo de la QPU

Estrategia 6: Suma Modular con Acarreo en Cascada (--oracle ripple)

Implementada en ripple_carry_shor.py. Usa sumadores con acarreo en cascada CDKM (Cuccaro et al. 2004) para las sumas de puntos controladas, reemplazando tanto las matrices unitarias densas como los circuitos de transposición descompuestos en ciclos.

En la codificación por índice de grupo, el punto P = kG se representa por su índice k en el grupo cíclico. Sumar S = sG se convierte en suma modular de la constante clásica s (mod n). La idea clave: cada suma de puntos controlada se reduce a una única suma modular controlada de una constante conocida, implementada mediante CDKMRippleCarryAdder e IntegerComparator de Qiskit.

El oráculo consiste en 2m sumas modulares controladas (m por registro de conteo), donde cada suma modular controlada realiza:

1. Cargar constante en un registro ancilla mediante CX desde el qubit de control
2. Semi-sumador CDKM para sumar la ancilla al acumulador (solo puertas de vecino más cercano)
3. Comparador de enteros para detectar desbordamiento (acc >= n)
4. Resta condicional de n mediante suma controlada por bandera de 2^m1 - n
5. Descomputación de bandera mediante sondeo basado en acarreo

No se utiliza conocimiento de la clave privada d en la construcción del circuito. Los índices de grupo para las potencias de G se calculan como 2^i mod n (público). Los índices de grupo para las potencias de Q se derivan de la enumeración pública del grupo cíclico generado por G — el punto Q se busca en esta enumeración.

• Codificación: Índice de grupo (0..n-1)
• Qubits: 4m + 5 donde m = ceil(log2(n))
• Puertas por suma: O(m) operaciones CDKM, cada una con O(m) puertas CX
• Escalado CX total: O(m^3)
• Mapeo a hardware: CDKM usa solo puertas de vecino más cercano, dando una sobrecarga de enrutamiento de ~1x en la topología heavy-hex de IBM (frente a 26-33x para sumadores basados en QFT)

Comparación

Primitivas Aritméticas QFT

El código incluye componentes modulares basados en QFT (sumadores Beauregard/Draper, multiplicación modular cuántico-cuántico, inversa/negación modular) como base para una codificación de coordenadas completamente aritmética a 256 bits. Estas primitivas se han verificado como correctas mediante simulación Statevector para primos hasta p=13.

Resultados

Se recuperaron con éxito claves privadas en hardware IBM Quantum para curvas del desafío de hasta 17 bits:

Todas las ejecuciones se realizaron en el plan de instancia abierta de IBM Quantum, que otorga 10 minutos de computación cuántica gratuita al mes. Los registros completos de ejecución se encuentran en la carpeta executions/.

La estrategia de acarreo en cascada (Estrategia 6) permitió un gran salto: de 10 bits (40 qubits, 2M puertas) a 17 bits (69 qubits, 112K puertas) — un aumento de 7 bits en el tamaño de clave con una reducción de 18x en el recuento de puertas de dos qubits. La estructura de puertas de vecino más cercano del sumador CDKM se mapea eficientemente a la topología heavy-hex de IBM, manteniendo la sobrecarga de enrutamiento cerca de 1x.

EP Semiclásica: Circuitos Dinámicos en Hardware IBM

La estrategia semiclásica (--oracle google) recuperó con éxito claves a 4, 6 y 7 bits usando circuitos dinámicos (reset en medio del circuito, puertas p condicionadas clásicamente mediante if_test) en procesadores IBM Heron r2. A 7 bits, el circuito usa solo 14 qubits (frente a 26 para el enfoque de permutación estándar) mientras produce recuentos de puertas 2Q comparables después de la transpilación.

A 8 bits y superiores, el enfoque semiclásico se vuelve impracticable en el hardware actual de IBM. Aunque if_else y reset son compatibles en Heron r2 (confirmado mediante inspección del backend objetivo), cada punto de realimentación clásica requiere una sincronización completa de la QPU — los 156 qubits físicos deben estar inactivos mientras el controlador clásico procesa la condicional para los ~16 qubits activos. Con ~295K puertas CZ distribuidas en 16+ puntos de realimentación, la sobrecarga de ejecución por disparo hace que los trabajos superen el presupuesto de tiempo de la QPU. El enfoque de permutación estándar, que ejecuta el mismo recuento de puertas en un único lote continuo sin circuitos dinámicos, se completa con éxito a esta escala.

Una truncación aproximada del QFT (parámetro max_corrections) reduce el número de bloques if_else de O(n^2) a O(n) reteniendo solo las correcciones de fase más cercanas k por paso de medición (los ángulos más allá de k contribuyen < pi/2^{k+1}, por debajo del piso de ruido del hardware). Con max_corrections=1, el circuito de 8 bits tiene 16 bloques if_else — aún suficientes para causar tiempo de espera agotado en hardware IBM con este recuento de puertas.

Análisis de Ruido y Fidelidad

Fidelidad Estimada del Circuito

Suponiendo una fidelidad típica de puerta de dos qubits (CX) de ~99.5% en IBM Quantum, la fidelidad estimada del circuito disminuye exponencialmente con el recuento de puertas:

La fidelidad del circuito se calcula como F ≈ (0.995)^{CX_count}. Para todo más allá de 4 bits, la fidelidad estimada es astronómicamente pequeña — la distribución de salida está abrumadoramente dominada por el ruido.

Por Qué Sigue Funcionando

Para 8 bits y superiores, cada disparo produce una cadena de bits casi única (8,128 resultados únicos de 8,192 disparos a 8 bits; los 20,000 únicos a 16 y 17 bits). La salida es indistinguible de un muestreo aleatorio uniforme a nivel de cadena de bits. Sin embargo, el algoritmo aún recupera la clave privada correcta.

La idea clave es que el posprocesamiento de Shor es robusto al ruido de una manera que el análisis de cadenas de bits en bruto no lo es. Cada disparo produce un triple de medición (j, k, r). La extracción calcula d_cand = (r - j) · k^{-1} mod n y verifica mediante d_cand · G == Q. Solo el verdadero d pasa la verificación EC, por lo que incluso un solo candidato correcto entre miles de disparos ruidosos es suficiente.

Un triple (j, k, r) puramente aleatorio produce el d_cand correcto con probabilidad ~1/n. Con S disparos, el número esperado de aciertos verificados solo del ruido es ~S/n. A 17 bits (n=65,173, S=20,000), esto da ~0.3 aciertos de ruido esperados — cualquier recuperación exitosa a esta escala proporciona evidencia de señal cuántica más allá del piso de ruido clásico.

Para las curvas más pequeñas donde disparos >> n (por ejemplo, 10 bits con n=547 y 1,024 disparos), el piso de ruido es ~1,024/547 ≈ 1.9 votos por candidato. Incluso un puñado de disparos portadores de señal empuja el d correcto por encima del piso de ruido. Esto explica cómo el algoritmo tiene éxito a pesar de fidelidades de circuito que harían parecer imposible la computación.

Señal Cuántica vs Ruido Clásico

A escala de juguete, el paso de verificación de la extracción (d_cand * G == Q) actúa como un filtro que acepta solo el d verdadero. Esto significa que incluso triples (j, k, r) puramente aleatorios producirán candidatos válidos a una tasa de aproximadamente disparos / n por ejecución. Cuando disparos >> n, el ruido aleatorio por sí solo puede recuperar d con alta probabilidad.

Para probar si el circuito cuántico contribuye señal más allá de este piso de ruido clásico, ejecutamos el desafío de 6 bits (n=31) con solo 8 disparos (muy por debajo del orden del grupo) 10 veces en ibm_kingston:

Resultado: 4/10 éxitos (40%) frente a una línea base de ruido clásico de ~20% (calculada mediante simulación Monte Carlo: 8 cadenas de bits aleatorias con (r-j)*k_inv mod 31 filtradas por verificación). Prueba binomial unilateral: P(X >= 4 | n=10, p=0.20) = 0.121, lo que indica una mejora de 2x sobre el piso de ruido. Aunque no es estadísticamente significativo individualmente a p < 0.05 (que requeriría 5+ éxitos), la tasa observada es consistente con una señal cuántica que contribuye aproximadamente 1-2 pares (j, k) válidos adicionales por ejecución más allá de lo que proporciona el azar.

Este resultado se sitúa entre el piso de ruido clásico y el régimen de ventaja cuántica teórica. En tamaños de curva más grandes donde n >> disparos, la línea base de ruido cae por debajo del 1% y cualquier recuperación exitosa de clave se convierte en evidencia sólida de computación cuántica.

Inicio 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

### Cómo ejecutar

Necesitas una cuenta de [IBM Quantum](https://quantum.ibm.com/). Proporciona tu API token en la primera ejecución y se guardará 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

Opciones de CLI

Estructura del proyecto```

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

## Referencias

- 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)

## Licencia

Este proyecto es una presentación para el Q-Day Prize Challenge publicado bajo [LICENCIA MIT](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE)