Introducción a la Computación Cuántica · Alonso Toro

RSA y el algoritmo de Shor

¿Qué tienen que ver cuatro picos en un histograma con la clave que permite leer un mensaje cifrado?

Abrir la conversación

Mensajes entre Rulito y Mitcha

Publica las claves y escribe por turnos. Las caras de cada burbuja indican quién puede ver ese paso. Tú puedes seguir las tres perspectivas.

Rulito

Clave pública sin anunciar

Gary

Sin mensajes interceptados

Mitcha

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.

    Código de la conversación y de la simulación

    El navegador sigue el intercambio RSA y comprueba los denominadores mediante exponenciación modular. Ver el JavaScript

    Leer la deducción de los picos

    Cómo se construye una clave RSA

    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.

    $$\begin{aligned}N&=pq, & \varphi(N)&=(p-1)(q-1),\\ \gcd(e,\varphi(N))&=1.\end{aligned}$$ $$\begin{aligned}ed&\equiv1\pmod{\varphi(N)},\\c&\equiv m^e\pmod N,\\m&\equiv c^d\pmod N.\end{aligned}$$

    Las cuentas de quien recibe el mensaje

    1. Escoger los primos. Tomemos 3 y 11. Su producto, 33, fija el conjunto de mensajes posibles: los enteros de 0 a 32.
    2. Contar los residuos coprimos. De los enteros entre 1 y 33, once son múltiplos de 3 y tres son múltiplos de 11. El 33 pertenece a ambos grupos. Quedan 33 − 11 − 3 + 1 = 20 coprimos. Esa cuenta explica el valor φ(33) = (3 − 1)(11 − 1).
    3. Elegir los exponentes. El 3 sirve como exponente público porque mcd(3, 20) = 1. Para encontrar su inverso usamos Euclides: 20 = 6 × 3 + 2 y 3 = 2 + 1. Sustituyendo, 1 = 7 × 3 − 20. Por eso el exponente privado es 7.

    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.

    Por qué recuperamos el mensaje

    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?

    Cómo se hace visible un período

    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.

    El oráculo de los primeros experimentos

    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.

    Qiskit · Oráculo reversible para x módulo el período
    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 gate

    Del circuito a la probabilidad

    El 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.

    Qiskit · Preparación, oráculo, QFT y lectura del control
    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
    Salida de Qiskit · Dos registros de cuatro qubits en el experimento periódico
         ┌───┐┌──────────┐             ░ ┌───────┐┌─┐         
    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.

    Qiskit · La QFT construida puerta a puerta en el cuaderno
    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
    Salida de Qiskit · Descomposición para tres qubits
    ┌───┐   
    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.

    De la función periódica a los picos de Fourier

    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.

    Preparación y medición

    $$|\psi_1\rangle=\frac{1}{\sqrt M}\sum_{x=0}^{M-1}|x\rangle|0\rangle.$$ $$U_f|x\rangle|z\rangle=|x\rangle|z\oplus f(x)\rangle.$$ $$|\psi_2\rangle=\frac{1}{\sqrt M}\sum_{x=0}^{M-1}|x\rangle|f(x)\rangle.$$

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

    $$L_s=\begin{cases}q+1 & s<b,\\q & s\ge b.\end{cases}$$ $$\Pr(f(s))=\frac{L_s}{M}.$$ $$|\psi_s\rangle=\frac{1}{\sqrt{L_s}}\sum_{k=0}^{L_s-1}|s+kr\rangle.$$

    Sumar fases complejas

    $$\operatorname{QFT}_M|x\rangle=\frac{1}{\sqrt M}\sum_{y=0}^{M-1}e^{2\pi ixy/M}|y\rangle.$$ $$\alpha_y(s)=\frac{e^{2\pi isy/M}}{\sqrt{L_sM}}\sum_{k=0}^{L_s-1}e^{ik\theta_y}.$$ $$\theta_y=\frac{2\pi ry}{M}.$$ $$P(y\mid s)=\frac{1}{L_sM}\left|\sum_{k=0}^{L_s-1}e^{ik\theta_y}\right|^2.$$

    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.

    $$P(y\mid s)=\begin{cases}1/r & y\in\{0,M/r,\ldots\},\\0 & \text{en otro caso}.\end{cases}$$

    Un pico y un cero, calculados a mano

    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.

    Explorar las fases de una rama

    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.

    Cuando el período no divide el registro

    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.

    $$\begin{aligned}S_L&=\frac{1-e^{iL\theta_y}}{1-e^{i\theta_y}}\\[4pt]&=e^{i(L-1)\theta_y/2}\frac{\sin(L\theta_y/2)}{\sin(\theta_y/2)}.\end{aligned}$$ $$P(y\mid s)=\frac{\sin^2(\pi L_s r y/M)}{L_sM\sin^2(\pi r y/M)}.$$

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

    $$P(y\mid s)\approx \frac{L_s}{M}\operatorname{sinc}^2(L_s\delta).$$ $$P(y)=\sum_{s=0}^{r-1}\frac{L_s}{M}\,P(y\mid s).$$

    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

    Laboratorio de Fourier

    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.

    Distribución de las salidas
    Frecuencia medidaProbabilidad teórica
    Resultado del registro de control (y)
    Consultar conteos y probabilidades
    Salida yConteoMedidaTeórica

    Código JavaScript del histograma

    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.

    Recalcular el histograma con Python

    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.

    Qué buscar al cambiar de función

    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.

    Qiskit Aer · Simulación del período 4 y lectura de los conteos
    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.

    $$\frac{5}{16}=\frac{1}{3+1/5}\approx\frac{1}{3}.$$ $$\frac{11}{16}=\frac{1}{1+1/(2+1/5)}\approx\frac{2}{3}.$$

    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.

    Comparación con los histogramas de Qiskit Aer

    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.

    Barras en las salidas 0, 4, 8 y 12
    Período 4 · 5000 disparos de Aer
    Picos en 0, 5 y 11 con conteos menores en los enteros vecinos
    Período 3 · 2000 disparos de Aer
    Cuatro picos en las salidas 0, 4, 8 y 12
    7 elevado a x módulo 15 · 100 disparos de Aer

    Del orden modular a los factores

    Qué escribe el oráculo modular

    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.

    Qiskit · Oráculo empleado para 7ˣ mod 15
    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 gate

    Si \(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)\).

    $$7^4\equiv 1\pmod{15},\qquad u=7^{4/2}\bmod 15=4.$$ $$\begin{aligned}\gcd(4-1,15)&=3,\\ \gcd(4+1,15)&=5.\end{aligned}$$

    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.

    Volver al mensaje 31

    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.

    Reproducir el proyecto en Qiskit

    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.ipynb

    Descargar 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.