Factorizar encontrando un periodo

Multiplicar dos primos de trescientas cifras le lleva a un ordenador microsegundos. Deshacer el producto, recuperar los primos a partir del resultado, les llevaría a los mejores algoritmos clásicos conocidos más tiempo que la edad del universo. Sobre esa asimetría descansa RSA (Rivest, Shamir y Adleman, 1977), el criptosistema que protege buena parte de las comunicaciones del mundo. En 1994 Peter Shor, en los Laboratorios Bell, demostró que un ordenador cuántico suficientemente grande lo rompería.

§Un poco de teoría de números

Trabajamos módulo $N$: dos enteros son congruentes, $a\equiv b(\mathrm{mod}N)$, si $N$ divide a $a-b$. Los números coprimos con $N$ forman un grupo con la multiplicación, ${\mathbb{Z}}_N^{\ast }$, con $\phi (N)$ elementos ($\phi$ es la función de Euler).

RSA usa $N=pq$ y, con $\phi (N)=(p-1)(q-1)$, elige un exponente de cifrado $e$ y otro de descifrado $d$ con $ed\equiv 1(\mathrm{mod}\phi (N))$. Conociendo $p$ y $q$, calcular $d$ es fácil; sin ellos, nadie sabe hacerlo de forma eficiente. El mejor algoritmo clásico de factorización, la criba general del cuerpo de números, tarda un tiempo del orden de

subexponencial pero enorme: factorizar el número de 829 bits RSA-250 en 2020 costó unos 2700 años-núcleo de cálculo.

§De factorizar a buscar periodos

La primera idea del algoritmo de Shor es clásica y se remonta a Gary Miller (1976): si sabemos calcular órdenes, sabemos factorizar.

Por qué funciona el máximo común divisor

Como $a^r\equiv 1$, $N$ divide a $a^r-1=(a^{r/2}-1)(a^{r/2}+1)$. No divide al primer factor, porque $r$ es el menor exponente con $a^r\equiv 1$; ni al segundo, por hipótesis. Así que $N$ comparte un factor no trivial con cada uno, que el algoritmo de Euclides encuentra en tiempo polinómico. La cota de probabilidad sale del teorema chino del resto: los órdenes de $a$ módulo cada potencia de primo se comportan de forma independiente.

Todo se reduce a encontrar el periodo $r$ de $f(x)=a^{x}modN$. Clásicamente, esto es tan difícil como factorizar. Cuánticamente, es un trabajo para la transformada de Fourier.

§El cálculo cuántico del orden

1. Se preparan dos registros y se pone el primero, de $t$ qubits con $N^2\le Q=2^t<2N^2$, en superposición uniforme: $\frac{1}{\sqrt{Q}}\sum _{x=0}^{Q-1}|x⟩|0⟩$.
2. Se calcula $f$ de forma reversible en el segundo registro: $\frac{1}{\sqrt{Q}}\sum _x|x⟩|a^{x}modN⟩$. La exponenciación modular se hace por cuadrados sucesivos, con $O(n^3)$ puertas para números de $n$ bits; es la parte más cara del algoritmo.
3. Se mide el segundo registro (o simplemente se olvida). El primero colapsa a un estado uniforme sobre una progresión aritmética $x_0,x_0+r,x_0+2r,\dots$: un estado periódico de periodo $r$.
4. Se aplica la QFT al primer registro y se mide. El resultado $y$ está, con alta probabilidad, cerca de un múltiplo de $Q/r$: $|\frac{y}{Q}-\frac{\ell }{r}|\le \frac{1}{2Q}$ para algún $\ell$.

El último paso es recuperar $r$ a partir de la fracción $y/Q$, un problema de teoría de números de más de dos mil años: aproximar un número con fracciones de denominador pequeño.

Como $\frac{1}{2Q}\le \frac{1}{2N^2}<\frac{1}{2r^2}$, la fracción $\ell /r$ (irreducible) aparece entre las reducidas de $y/Q$, que se calculan con el algoritmo de Euclides. Si $\ell$ y $r$ resultan ser coprimos, lo que ocurre con probabilidad $\mathrm{\Omega }(1/\log \log r)$, el denominador es el orden $r$. Bastan unas pocas repeticiones.

§¿Cuánto falta?

En 2001 un equipo de IBM factorizó $15=3\times 5$ con siete espines nucleares de una molécula. Desde entonces el récord de implementaciones honestas apenas se ha movido: el algoritmo de Shor necesita muchos qubits de alta calidad y circuitos muy largos, es decir, corrección de errores. Las estimaciones de recursos para RSA-2048 no han parado de bajar: unos 20 millones de qubits físicos durante 8 horas (Gidney y Ekerå, 2019), y menos de un millón de qubits ruidosos en menos de una semana (Gidney, 2025). Los procesadores actuales tienen del orden de cien a mil.

La amenaza se toma en serio, porque los datos cifrados se pueden guardar hoy y descifrar en el futuro. En 2024 el NIST publicó los primeros estándares de criptografía poscuántica (FIPS 203, 204 y 205), basados en problemas sobre retículos y funciones resumen para los que no se conoce ningún algoritmo cuántico eficiente. La lección matemática del algoritmo de Shor va más allá de la criptografía: los ordenadores cuánticos son extraordinariamente buenos encontrando estructura periódica oculta en grupos abelianos (el problema del subgrupo oculto), y nadie sabe si ese poder llega mucho más lejos.

§Referencias

1. R. L. Rivest, A. Shamir y L. Adleman (1978). «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems». Communications of the ACM, 21(2).
2. G. L. Miller (1976). «Riemann's Hypothesis and Tests for Primality». Journal of Computer and System Sciences, 13(3).
3. P. W. Shor (1994). «Algorithms for quantum computation: discrete logarithms and factoring». FOCS (versión de revista: SIAM J. Computing, 1997).
4. L. M. K. Vandersypen et al. (2001). «Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance». Nature, 414.
5. C. Gidney y M. Ekerå (2021). «How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits». Quantum, 5 (arXiv 2019).
6. C. Gidney (2025). «How to factor 2048 bit RSA integers with less than a million noisy qubits». Preprint en arXiv.
7. NIST (2024). FIPS 203, 204 y 205: estándares de criptografía poscuántica.