Rulito
Clave pública sin anunciar
Introducción a la Computación Cuántica · Alonso Toro
¿Qué tienen que ver cuatro picos en un histograma con la clave que permite leer un mensaje cifrado?
Abrir la conversaciónPublica las claves y escribe por turnos. Las caras de cada burbuja indican quién puede ver ese paso. Tú puedes seguir las tres perspectivas.
Clave pública sin anunciar
Sin mensajes interceptados
Clave pública sin anunciar
Los módulos de esta escena tienen ocho bits. Ciframos bloques con RSA sin relleno. Para buscar el orden, la simulación usa ocho qubits de destino y 16 de control, por lo que hay \(M=2^{16}=65\,536\) posibles lecturas del control.
Elige un mensaje interceptado. Gary trabaja con la clave pública que se usó al enviarlo, aunque Mitcha anuncie otra después.
Para recuperar cada bloque, Gary tiene que calcular \(m=c^d\bmod N\). Ya tiene \(c\) y \(N\). Le falta el exponente privado \(d\).
Con los factores \(p\) y \(q\) de \(N\) puede calcular \(\varphi(N)=(p-1)(q-1)\) y obtener \(d\) como el inverso de \(e\) módulo \(\varphi(N)\).
El gráfico muestra la probabilidad de cada lectura \(y\). Los picos están cerca de \(kM/r\). Una lectura cerca de un pico da \(y/M\approx k/r\). Gary prueba los denominadores de los convergentes de \(y/M\) y comprueba cuáles hacen que \(a^r\bmod N=1\).
La vista general agrupa salidas vecinas. La ampliación muestra una barra por entero. Si \(k\) y \(r\) comparten un factor, la fracción reducida puede dar un divisor de \(r\). Gary puede tomar otra lectura.
Toma una lectura y sigue sus convergentes.
| Lectura \(y\) | Convergentes probados | Comprobación |
|---|
Si \(r\) es par, \(u=a^{r/2}\bmod N\) cumple \(u^2\equiv1\pmod N\). Por eso \(N\) divide \((u-1)(u+1)\). Cuando \(u\) es distinto de \(1\) y \(-1\) módulo \(N\), cada factor del producto comparte un primo distinto con \(N\).
Gary usa el exponente público \(e\) y calcula su inverso módulo \(\varphi(N)\).
Repite la operación con cada bloque y vuelve a interpretar los bytes como UTF-8.
El navegador sigue el intercambio RSA y comprueba los denominadores mediante exponenciación modular. Ver el JavaScript
En el servidor, Python construye el estado de control de cada rama a partir del residuo del oráculo. Aer ejecuta el circuito QFT de 16 qubits sobre esos estados y simula las mediciones. El peso de cada rama cuenta cuántas entradas dieron ese residuo. Ver el código Qiskit
En RSA, quien recibe los mensajes elige dos primos distintos, p y q, y publica su producto N junto con un exponente e. Cualquiera puede representar un mensaje por un entero entre 0 y N − 1 y calcular el resto de elevarlo a e. Para deshacer esa operación se necesita un exponente privado d.
Guardemos ese 31. Si conseguimos los factores de 33, podremos calcular φ(N) = (p − 1)(q − 1) y elegir d de modo que ed deje resto 1 al dividirlo por φ(N). El ejemplo usa la operación elemental de RSA sobre enteros pequeños. Los esquemas de cifrado como RSAES-OAEP incorporan además una codificación del mensaje.
Las celdas editables ejecutan Python en el navegador. Pulsa «Ejecutar» o Mayús + Intro. La primera ejecución requiere conexión para descargar el intérprete. Prueba otro mensaje entre 0 y 32.
Cifrar y luego descifrar equivale a elevar 4 a la potencia 3 × 7 = 21. Como 4 es coprimo con 33, el teorema de Euler da 4²⁰ ≡ 1 (mod 33). Por tanto, 4²¹ ≡ 4. Para un mensaje divisible por uno de los primos, la igualdad se verifica módulo cada primo por separado: en el primo que lo divide, ambos lados valen cero; en el otro se aplica el pequeño teorema de Fermat. El teorema chino del resto reúne las dos congruencias.
La persona que cifra solo necesita (33, 3). El cálculo de φ muestra por qué conocer la factorización basta para reconstruir un exponente privado. Ahora cambiamos de punto de vista: ¿qué información entrega el circuito para poder factorizar?
El cuaderno empieza con dos registros. Cuatro qubits de control dan 16 entradas posibles. Las puertas Hadamard preparan una superposición uniforme. Un oráculo reversible escribe f(x) en el registro de destino mediante XOR y conserva la entrada x. La matriz de 16 × 16 del ensayo previo con dos qubits por registro muestra esa reversibilidad: cada columna envía un estado de base a una fila distinta.
Imagina que f(x) = x mod 4 y que al medir el destino obtienes 1. En el control quedan las entradas 1, 5, 9 y 13. Una medición directa devolvería solo una. La transformada de Fourier cuántica (QFT) hace que sus amplitudes interfieran. Para la salida 4, dos entradas separadas por cuatro posiciones aportan fases separadas por una vuelta entera. Se refuerzan. Lo mismo sucede en 0, 8 y 12.
Para probar un período conocido, el cuaderno recorre las entradas y escribe el residuo de cada una. La cadena binaria ctrl_str selecciona el valor de entrada que activa las puertas X del destino.
def oraculo_periodico(periodo, n_control, n_target=None):
if periodo > 2**n_target:
raise ValueError(
f"n_target={n_target} es muy chico para periodo={periodo} "
f"(se requieren al menos {max(1, (periodo - 1).bit_length())} qubits)."
)
circ = QuantumCircuit(n_control + n_target)
controles = list(range(n_control))
for x in range(2**n_control):
y = x % periodo
ctrl_str = format(x, f'0{n_control}b')
for bit_idx in range(n_target):
if (y >> bit_idx) & 1:
circ.mcx(controles, n_control + bit_idx, ctrl_state=ctrl_str)
gate = circ.to_gate()
gate.name = f"x mod {periodo}"
return gateEl circuito construye la QFT con puertas Hadamard, rotaciones de fase controladas e intercambios que ordenan los bits. Para una rama de longitud L, la amplitud en y es la suma de exp(2πixy/16) sobre las entradas de esa rama, dividida por √(16L). El módulo al cuadrado da la probabilidad. Un desplazamiento común cambia la fase de la suma, pero conserva su módulo.
El destino distingue las ramas. Para obtener el histograma del control se suman sus probabilidades, cada una ponderada por L/16. Medir primero el destino y descartar su lectura produce la misma distribución que omitir esa medición. El cuaderno utiliza ambas variantes.
def armar_circuito(oraculo_gate, n_control, n_target=None):
total_qubits = n_control + n_target
circ = QuantumCircuit(total_qubits, n_control)
circ.h(range(n_control))
circ.append(oraculo_gate, range(total_qubits))
circ.measure(range(n_control, total_qubits), range(n_target))
circ.barrier()
circ.append(QFT(n_control), range(n_control))
circ.measure(range(n_control), range(n_control))
return circ ┌───┐┌──────────┐ ░ ┌───────┐┌─┐
q_0: ┤ H ├┤0 ├─────────────░─┤0 ├┤M├─────────
├───┤│ │ ░ │ │└╥┘┌─┐
q_1: ┤ H ├┤1 ├─────────────░─┤1 ├─╫─┤M├──────
├───┤│ │ ░ │ QFT4 │ ║ └╥┘┌─┐
q_2: ┤ H ├┤2 ├─────────────░─┤2 ├─╫──╫─┤M├───
├───┤│ │ ░ │ │ ║ ║ └╥┘┌─┐
q_3: ┤ H ├┤3 ├─────────────░─┤3 ├─╫──╫──╫─┤M├
└───┘│ x mod 4 │┌─┐ ░ └───────┘ ║ ║ ║ └╥┘
q_4: ─────┤4 ├┤M├──────────░───────────╫──╫──╫──╫─
│ │└╥┘┌─┐ ░ ║ ║ ║ ║
q_5: ─────┤5 ├─╫─┤M├───────░───────────╫──╫──╫──╫─
│ │ ║ └╥┘┌─┐ ░ ║ ║ ║ ║
q_6: ─────┤6 ├─╫──╫─┤M├────░───────────╫──╫──╫──╫─
│ │ ║ ║ └╥┘┌─┐ ░ ║ ║ ║ ║
q_7: ─────┤7 ├─╫──╫──╫─┤M├─░───────────╫──╫──╫──╫─
└──────────┘ ║ ║ ║ └╥┘ ░ ║ ║ ║ ║
c: 4/══════════════════╩══╩══╩══╩══════════════╩══╩══╩══╩═
0 1 2 3 0 1 2 3 La primera medición guarda el destino en bits clásicos. La última escribe encima la lectura del control. Por eso el histograma contiene valores de y. En el experimento modular se omite la primera medición.
def QFT(n):
# n := numero de qubits
qft_circuit = QuantumCircuit(n)
for i in range(n-1, -1, -1):
qft_circuit.h(i)
for j in range(i-1, -1, -1):
qft_circuit.cp(pi/2**(i-j), j, i)
for i in range(n//2):
qft_circuit.swap(i, n-i-1)
puerta = qft_circuit.to_gate()
puerta.name = "QFT" + str(n)
return puerta┌───┐
q_0: ───────────────■─────────────■───────┤ H ├─X─
│ ┌───┐ │P(π/2) └───┘ │
q_1: ──────■────────┼───────┤ H ├─■─────────────┼─
┌───┐ │P(π/2) │P(π/4) └───┘ │
q_2: ┤ H ├─■────────■───────────────────────────X─
└───┘La línea cp(π/2ᵏ, …) gira la fase de forma condicionada. La distancia entre los qubits determina el ángulo: aparecen π/2 para vecinos y π/4 al separarlos dos posiciones. Los intercambios del final invierten el orden de los bits.
Usaremos \(n\) para los qubits de control, \(M=2^n\) para las entradas, \(r\) para el período y \(s\) para el primer índice de la rama observada. Cada clase dentro de un período da un valor distinto del oráculo en estos experimentos.
Si \(M=qr+b\) con \(0\le b<r\), hay \(q\) períodos completos y un tramo de \(b\) entradas. Los índices de la rama \(s\) son \(s+kr\). El tramo final añade una entrada solo cuando \(s<b\).
En la regla de Born, la fase común \(e^{2\pi isy/M}\) desaparece porque tiene módulo uno. Si el período encaja exactamente, \(L_s=M/r\). Las fases coinciden cuando \(\theta_y\) es múltiplo de \(2\pi\). Para las demás salidas, \(z=e^{i\theta_y}\ne1\) pero \(z^{L_s}=e^{2\pi iy}=1\). La suma geométrica \((1-z^{L_s})/(1-z)\) vale cero.
Fijemos la rama que comienza en 0 para ver solo el efecto de la separación. Sus entradas son 0, 4, 8 y 12. Para cualquier salida y, cada término gira un ángulo adicional Δ = 2π · 4y/16 respecto al anterior.
La normalización divide la suma por √(4 × 16) = 8. Al medir y = 4 se obtiene |4/8|² = 1/4; al medir y = 1 la probabilidad es cero. En otra rama, todos los términos giran juntos. La longitud de la suma se conserva.
Cada flecha representa una entrada de la rama que comienza en cero. Su dirección muestra la fase que aporta a la salida elegida. Prueba r = 4 con y = 1 y 4. Después prueba r = 3 con y = 5 para ver una alineación parcial.
Sea \(z=e^{i\theta_y}\). Multiplicar la suma \(S_L=1+z+\cdots+z^{L-1}\) por \(1-z\) deja \(1-z^L\). Al factorizar los ángulos medios con la identidad de Euler se obtiene la siguiente expresión.
Si se anula el denominador, los términos se alinean y el límite es \(P(y\mid s)=L_s/M\). Cerca de \(y=jM/r\), la desviación \(\delta=ry/M-j\) es pequeña. Usar \(\sin(\pi\delta)\approx\pi\delta\) da la aproximación del informe, con \(\operatorname{sinc}(u)=\sin(\pi u)/(\pi u)\).
Con período 3 y \(M=16\), las ramas tienen 6, 5 y 5 entradas. La rama de seis entradas tiene \(P(0\mid 0)=6/16\). Al sumar las ramas con sus pesos, el pico completo en cero vale \((6^2+5^2+5^2)/16^2=86/256\), aproximadamente 33,6 %. Los otros dos máximos se concentran cerca de \(16/3\) y \(32/3\).
Simulación en el navegador
Elige una función y ejecuta el experimento. Cada barra indica qué porcentaje de las mediciones dio ese valor de y. Los puntos marcan las probabilidades teóricas. Repite la ejecución para observar la variación del muestreo.
| Salida y | Conteo | Medida | Teórica |
|---|
| Salida y | Conteo | Medida | Teórica |
|---|
JavaScript agrupa las entradas por valor del destino, suma amplitudes de Fourier y muestrea la distribución resultante. El cuaderno descargable implementa los circuitos con puertas de Qiskit.
Esta celda calcula las amplitudes de Fourier por rama y toma muestras de la distribución. Cambia periodo = 3 a periodo = 4 y ejecútala para comparar. La función histograma muestra el gráfico debajo del código.
x mod 4. Los cuatro picos están separados por 4. El período se recupera dividiendo el tamaño del registro por ese paso: 16/4 = 4. El cuaderno emplea 5000 disparos.
x mod 3. Las ramas tienen 6, 5 y 5 entradas. Los máximos teóricos se sitúan cerca de 0, 16/3 y 32/3. La medición solo devuelve enteros, así que parte de la probabilidad se reparte entre vecinos incluso sin ruido. Las fracciones 5/16 y 11/16 se aproximan a 1/3 y 2/3. Su denominador sugiere el período. El ensayo de Aer emplea 2000 disparos y usa el período conocido para acotar la aproximación.
7ˣ mod 15. Las salidas del oráculo empiezan por 1, 7, 4, 13 y vuelven a 1. Es la misma separación de cuatro entradas con etiquetas de destino diferentes. El cuaderno ejecuta 100 disparos y luego introduce a mano las posiciones 4, 8 y 12 para desarrollar la extracción. Con orden 4, la raíz intermedia es 7² mod 15 = 4. Los máximos comunes divisores de 4 − 1 y 4 + 1 con 15 dan 3 y 5.
backend = AerSimulator()
job = backend.run(transpile(circ_ideal, backend), shots=5000)
result = job.result().get_counts()
# Convertimos las claves medidas a entero y rellenamos de 0 a M-1 (15) con 0 si no salieron
counts_dec = {int(k, 2): v for k, v in result.items()}
counts_todos = {i: counts_dec.get(i, 0) for i in range(2**n_control)}Los convergentes se obtienen al truncar las fracciones continuas después de la última división que nos aporta un denominador útil.
Una medición de 8 con M = 16 ilustra una ambigüedad: 8/16 se reduce a 1/2 aunque el orden de 7 módulo 15 es 4. Se perdió un factor al simplificar. La comprobación 7² mod 15 = 4 descarta la propuesta 2. Una lectura de 4 o de 12 sí da denominador 4.
Estos gráficos se generaron al ejecutar el cuaderno. Su eje vertical muestra conteos. El laboratorio de arriba usa frecuencias relativas para poder compararlas con las probabilidades teóricas.



Para cada entrada x, el bucle calcula el residuo y activa una X multicontrolada por cada bit que vale uno. Por ejemplo, para x = 2 el residuo es 4, o 0100 en binario. El destino que empieza en 0000 termina en 0100. La operación XOR permite deshacer esa escritura aplicando el mismo bloque otra vez.
def oraculo_modular(a, N, n_control, n_target):
total_qubits = n_control + n_target
circ = QuantumCircuit(total_qubits)
controles = list(range(n_control))
for x in range(2**n_control):
y = pow(a, x, N) # Equivalente a (a**x) % N, pero mucho más rápido
ctrl_str = format(x, f'0{n_control}b')
for bit_idx in range(n_target):
if (y >> bit_idx) & 1:
target_qubit = n_control + bit_idx
circ.mcx(controles, target_qubit, ctrl_state=ctrl_str)
gate = circ.to_gate()
gate.name = f"{a}^x mod {N}"
return gateSi \(a\) es coprimo con \(N\), el orden \(r\) es el menor entero positivo con \(a^r\equiv1\pmod N\). Si \(r\) es par, escribe \(u=a^{r/2}\bmod N\). Entonces \(u^2\equiv1\pmod N\) y \(N\) divide el producto \((u-1)(u+1)\).
Para \(N=pq\) con primos impares distintos, cada primo divide uno de los dos términos. Si \(u\not\equiv\pm1\pmod N\), los primos quedan en términos diferentes. Eso explica por qué cada máximo común divisor devuelve un factor propio.
Para el módulo 33 podemos comprobar la misma idea a mano. Con base 10, los residuos son 1, 10, 1: el orden es 2. Como 10² − 1 es múltiplo de 33, calculamos mcd(9, 33) = 3 y mcd(11, 33) = 11. Ya tenemos los primos. Entonces φ(33) = 20 y el exponente privado es 7, pues 3 × 7 = 21.
La simulación de Shor del cuaderno factoriza 15. El segundo módulo, 33, permite cerrar el ejemplo de RSA con exponentes distintos mediante un cálculo clásico. En un caso general, una lectura puede dar un divisor del orden o caer lejos del pico. Hay que comprobar el orden candidato y, si es impar o da una raíz trivial, ensayar otra base.
El oráculo del cuaderno enumera las entradas para que se pueda inspeccionar cada puerta. Una implementación escalable construye la exponenciación modular mediante multiplicaciones controladas. Esa diferencia importa al interpretar los tiempos del simulador.
El cuaderno contiene los circuitos de Qiskit, la simulación con Aer y el desarrollo matemático. Las celdas de esta página usan Python estándar para comprobar los cálculos y simular la distribución. Para repetir los experimentos, descarga el archivo y ejecuta estos comandos desde su carpeta. En JupyterLab, selecciona «Run All Cells».
python -m pip install jupyterlab qiskit==2.6.1 qiskit-aer==0.18.2 matplotlib numpy
python -m jupyterlab Proyecto_RSA_y_Shor.ipynbDescargar el cuaderno ejecutado · Leer la presentación original (PDF)
Para ejecutar el cuaderno en Google Colab, descárgalo, elige Archivo → Subir cuaderno y ejecuta primero %pip install qiskit==2.6.1 qiskit-aer==0.18.2 en una celda nueva. Luego ejecuta las celdas del proyecto. Abrir Google Colab
Referencias · artículo de Peter Shor y especificación de RSA.