yuvadm/quantumslopSolucionador cuántico para el Problema del Logaritmo Discreto en Curva Elíptica utilizando el algoritmo de Shor, implementando múltiples estrategias de oráculo para recuperar claves privadas ECC en hardware cuántico real.
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.
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:
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.
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).
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:
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.
--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 qubitsid_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.
--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:
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.
--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.
| Tamaño de curva | Qubits estándar | Qubits semiclásicos | Ahorro | Verificado en hardware |
|---|---|---|---|---|
| 4 bits (n=7) | 11 | 5 | 55% | Sí |
| 6 bits (n=31) | 17 | 7 | 59% | Sí |
| 7 bits (n=79) | 26 + anc | 14 | 46% | Sí |
| 8 bits (n=139) | 25 + anc | 10 + anc | 60% | No (sobrecarga de sincronización QPU) |
| 10 bits (n=547) | 31 + anc | 12 + anc | 61% | No (sobrecarga de sincronización QPU) |