¿Qué es el algoritmo de Shor?
El algoritmo de Shor es un algoritmo cuántico de tiempo polinómico desarrollado por el matemático Peter Shor en 1994, diseñado para descomponer números enteros en sus factores primos y calcular logaritmos discretos.
Ahora mismo, mientras lees estas líneas, tu navegador web casi con total seguridad está protegiendo la conexión mediante cifrado RSA. El acceso a tu banca online, tu correo electrónico, el pago con tarjeta en cualquier tienda digital... Todo descansa sobre un obstinado principio matemático: multiplicar dos números primos colosales es un juego de niños, pero descomponer el resultado de nuevo en sus factores originales resulta una tarea prácticamente inviable para cualquier ordenador clásico.
Esa asimetría es el cerrojo de nuestra seguridad digital. Y, en 1994, un matemático llamado Peter Shor dio con la llave maestra.
No construyó un ordenador cuántico. Ni siquiera necesitaba que existiera en ese momento. Se limitó a demostrar sobre el papel que, si algún día llegaba a construirse uno, este podría factorizar cifras astronómicas en tiempo polinómico. Es decir: convertir una tarea que a los superordenadores actuales les llevaría más tiempo que la edad del universo, en un cálculo que una máquina cuántica resolvería en lo que tardas en tomarte un café.
El mundo de la criptografía contuvo la respiración de golpe.
El callejón sin salida clásico y el escudo invisible de RSA
Para entender qué es el algoritmo de Shor, conviene recordar cómo funciona el cifrado RSA. Escoges dos números primos enormes (de unos 300 dígitos cada uno) y los multiplicas. Obtienes un número N de unos 600 dígitos. Hacer público N no compromete la seguridad; todo el sistema se basa en mantener en secreto los dos primos originales (p y q).
¿Por qué? Porque invertir esa multiplicación —descomponer N en sus factores— es el punto ciego de la computación clásica.
Imagínalo así: mezclar dos botes de pintura de distinto color lleva un segundo. Pero separar esa mezcla y devolverla con precisión quirúrgica a sus pigmentos originales resulta prácticamente imposible si no sabes cuáles eran desde el principio.
El algoritmo clásico más eficiente del que disponemos hoy en día es la criba general del cuerpo de números (GNFS, por sus siglas en inglés). Su complejidad temporal crece de forma subexponencial respecto al tamaño de N. Aunque suene mejor que un crecimiento puramente exponencial, sigue siendo catastróficamente lento para claves estándar de 2048 bits: hablamos de miles de millones de años de cómputo en los centros de datos más potentes del planeta. El espacio de búsqueda por fuerza bruta es sencillamente inabarcable.
Por eso RSA reinó con tranquilidad durante décadas. Hasta que Shor se hizo una pregunta aparentemente inocente: ¿y si dejamos de intentar factorizar de forma directa?
El genial cambio de enfoque de Shor
Aquí reside el salto conceptual que convierte al algoritmo de Shor en una obra de arte: no atacó la factorización de frente, sino que cambió el marco del problema.
En lugar de preguntarse «¿cuáles son los factores de N?», Shor planteó: «¿cuál es el periodo de una función periódica concreta?».
El procedimiento matemático es el siguiente: tomas un número arbitrario x que no comparta factores con N y calculas la secuencia:
x¹ mod N, x² mod N, x³ mod N, x⁴ mod N, …
La operación «mod N» devuelve el resto de la división entera entre N, igual que las agujas de un reloj. Tras las 12 en punto, no pasas a las 13, sino que vuelves a empezar en la 1. La aritmética modular es aritmética de reloj: funciona en bucles cerrados.
Y dado que funciona en bucle, la secuencia forzosamente tiene que repetirse tarde o temprano. El número de pasos que tarda en volver al inicio es lo que denominamos el periodo r.
Y aquí viene la clave: si consigues hallar ese valor r, y siempre que r sea un número par (lo cual ocurre la mayoría de las veces), los factores primos de N se obtienen de forma casi instantánea aplicando el máximo común divisor:
mcd(xr/2 − 1, N) y mcd(xr/2 + 1, N)
Un cálculo que un procesador convencional resuelve en milisegundos. El problema complejo (factorizar) se reduce a encontrar un periodo repetitivo. Y si hay algo en lo que la computación cuántica resulta letalmente eficaz, es precisamente en hallar periodicidades.
Al fin y al cabo, un periodo no es más que una cuestión de frecuencias. Y en el terreno de las frecuencias, la interferencia cuántica no tiene rival.
Los cuatro pasos: cómo se desata la magia cuántica
Paso 1: Preparación clásica
Antes de que intervenga el primer cúbit, un ordenador convencional elige un número aleatorio x comprendido entre 2 y N−1, y comprueba si mcd(x, N) = 1 mediante el algoritmo de Euclides. Si por pura casualidad el resultado es mayor que 1, habrás encontrado un factor por azar (algo estadísticamente insignificante con números grandes, pero un atajo que no cuesta nada comprobar).
Si el mcd es 1, pasamos a la fase cuántica.
Paso 2: Superposición masiva de estados
Se inicializa un registro cuántico de cúbits en una superposición uniforme de todos los valores de entrada posibles a la vez. Si disponemos de n cúbits, generamos 2n estados simultáneos.
Conviene no caer en la simplificación habitual de «probar todas las soluciones a la vez» al estilo clásico. Es más exacto imaginarlo así: dispones todas las entradas sobre una inmensa mesa matemática, y el circuito cuántico evalúa la exponenciación modular sobre todas ellas en un único paso operativo, codificando los resultados en las amplitudes de probabilidad del estado cuántico global.
El registro de salida alberga ahora una función periódica (xa mod N) para cada valor de a. Esa secuencia contiene un ritmo oculto: el periodo r. Sin embargo, está sepultado en una maraña de superposiciones superpuestas. No puedes limitarte a «mirar»; si mides el sistema en este punto, la función colapsará en un valor aleatorio inservible.
Hace falta extraer ese patrón sin destruir la estructura cuántica. Ahí entra en juego la Transformada Cuántica de Fourier.
Paso 3: La Transformada Cuántica de Fourier (QFT)
Este es el núcleo que la mayoría de manuales oculta tras fórmulas densas. Veámoslo con una analogía intuitiva.
Imagina una sala con un centenar de diapasones vibrando a frecuencias ligeramente distintas. Si los golpeas todos a la vez, el resultado acústico es puro caos: una masa de ruido ininteligible. Pero si contaras con un receptor capaz de amplificar solo aquellas ondas cuyas crestas coinciden y anular las que se interfieren, podrías aislar la frecuencia dominante al instante.
Eso es exactamente lo que la QFT hace con las amplitudes cuánticas.
Tras el paso 2, el estado cuántico contiene una señal periódica escondida entre miles de datos. La QFT aplica un cambio de base: traslada el estado del «dominio temporal» (qué entrada produjo qué salida) al «dominio frecuencial» (cuál es la longitud del ciclo que se repite).
El principio físico subyacente es la interferencia cuántica. Cada posible periodo aporta una onda con una fase determinada. Las trayectorias que corresponden a periodos incorrectos interfieren de forma destructiva (sus fases se cancelan mutuamente, igual que unos auriculares con cancelación activa de ruido neutralizan el sonido exterior). En cambio, las trayectorias asociadas al periodo correcto se alinean en fase, sumándose mediante interferencia constructiva y amplificando la probabilidad de ese resultado.
Al medir el registro tras la QFT, obtienes con una probabilidad altísima un valor directamente proporcional a 1/r. El ruido erróneo se ha silenciado por completo; la respuesta válida emerge con total claridad.
Ningún superordenador clásico puede replicar este mecanismo de interferencia con esa eficiencia. No es una cuestión de potencia bruta, sino de un paradigma de computación radicalmente distinto.
Paso 4: Medición y procesado clásico final
Se realiza la medición del registro y se obtiene un valor numérico. Mediante el método clásico de fracciones continuadas, se extrae el valor exacto de r. Acto seguido, se introduce r en las fórmulas del máximo común divisor y se obtienen los factores primos originales de N.
Si el periodo obtenido resulta ser impar (un fallo contemplado en la estadística del algoritmo), simplemente se regresa al Paso 1, se escoge otro valor de x y se repite la operación. Por término medio, basta un puñado de intentos para dar con la solución definitiva.
Computación clásica vs. computación cuántica
| Criterio | Algoritmo clásico (GNFS) | Algoritmo de Shor |
|---|---|---|
| Complejidad temporal | Subexponencial: ~exp(O((log N)1/3 (log log N)2/3)) | Polinómica: O((log N)³) |
| Estrategia fundamental | Búsqueda exhaustiva en cuerpos de números algebraicos | Búsqueda de periodos mediante interferencia cuántica |
| Requisitos de hardware | CPU/GPU clásicas (infraestructura existente) | Ordenador cuántico tolerante a fallos con miles de cúbits lógicos |
| Tiempo para romper RSA-2048 | Estimado en ~1017 años (miles de millones de veces la edad del universo) | Teóricamente cuestión de horas en hardware cuántico maduro |
| Cuello de botella | Explosión combinatoria del espacio de estados | Número de cúbits, tasas de error y fidelidad de puertas lógicas |
El abismo entre una complejidad «subexponencial» y una «polinómica» no es una simple mejora de rendimiento: marca la frontera entre lo computacionalmente imposible y lo trivial. Supone un auténtico salto de fase en la teoría de la computación.
¿Ha muerto definitivamente el cifrado RSA?
No, ni mucho menos a corto plazo. Y aquí es donde la ingeniería real modera las expectativas teóricas.
El algoritmo de Shor necesita ejecutarse sobre cúbits lógicos, es decir, unidades de información cuántica totalmente protegidas contra errores. El hardware disponible hoy en día solo proporciona cúbits físicos, propensos al ruido térmico, la decoherencia y las imperfecciones de control. Para implementar un único cúbit lógico estable, se necesitan entre cientos y miles de cúbits físicos dedicados exclusivamente a códigos de corrección cuántica de errores.
Para romper una clave RSA de 2048 bits, los cálculos más rigurosos estiman que harían falta entre 4.000 y 20.000 cúbits lógicos (según la arquitectura del procesador y el esquema de corrección empleado). Esto se traduce en una máquina de millones de cúbits físicos operando con fidelidades de puerta por encima del 99,9 %.
En la actualidad, los procesadores cuánticos más avanzados rondan entre los 1.000 y 1.500 cúbits físicos, con niveles de ruido que aún sitúan la computación a gran escala tolerante a fallos como un reto de ingeniería a medio o largo plazo. No obstante, la amenaza no puede ignorarse: agencias estatales y grandes organizaciones pueden interceptar y almacenar tráfico cifrado hoy para descifrarlo en el futuro, una táctica conocida como «harvest now, decrypt later» (recopilar ahora, descifrar después). Por esta razón, la transición hacia la Criptografía Poscuántica (PQC) ya está en marcha. El NIST estadounidense publicó en 2024 sus primeros estándares de cifrado poscuántico, basados en retículos algebraicos y funciones hash inmunes a los ataques cuánticos.
La transición tecnológica ya ha comenzado: de forma gradual, compleja, pero imparable.
Preguntas frecuentes
¿Es el algoritmo de Shor de tiempo polinómico?
Sí. Su complejidad temporal es de O((log N)³), lo que significa que crece de forma polinómica en función del número de dígitos de N. Este rendimiento lo convierte en un hito histórico: los métodos clásicos de factorización son superpolinómicos, por lo que el algoritmo de Shor no es simplemente más rápido, sino que pertenece a una clase de complejidad computacional radicalmente superior.
¿Puede el algoritmo de Shor romper el cifrado AES-256?
No. El algoritmo de Shor está diseñado específicamente para problemas basados en factorización de enteros y logaritmos discretos (como RSA, Diffie-Hellman o la criptografía de curva elíptica). AES es un algoritmo de cifrado simétrico. Frente a AES, los ordenadores cuánticos emplean el algoritmo de Grover, que solo ofrece una aceleración cuadrática: reduce la seguridad efectiva de AES-256 al equivalente de AES-128. No rompe el algoritmo; basta con duplicar la longitud de la clave para mantenerlo blindado.
¿Por qué los superordenadores clásicos no pueden simular el algoritmo de Shor?
Porque la Transformada Cuántica de Fourier opera sobre un espacio de estados que crece de forma exponencial con cada cúbit adicional. Simular el comportamiento de apenas 300 cúbits exigiría rastrear 2300 amplitudes complejas en memoria, una cifra superior al número de átomos presentes en todo el universo observable. El patrón de interferencias que permite funcionar al algoritmo de Shor es un fenómeno cuántico puro que carece de equivalente clásico eficiente.
Reflexión final
La lección más profunda que nos deja el algoritmo de Shor trasciende la propia criptografía: atañe a la naturaleza misma de lo que consideramos computable.
Antes de 1994, asumíamos que ciertos problemas eran intrínsecamente difíciles porque exigían explorar un espacio de posibilidades inmenso. Shor demostró que muchos de esos problemas solo resultaban imposibles porque nuestros ordenadores clásicos carecían del marco conceptual y físico adecuado. Si dotas a una máquina de superposición e interferencia cuántica, lo que parecía la búsqueda desesperada de dos granos de arena concretos en un desierto se convierte en algo tan elegante como escuchar la frecuencia exacta en la que resuena una cuerda.
El hardware terminará por llegar. Quizá en una década, quizá en dos. Cuando lo haga, las cerraduras matemáticas en las que hemos confiado durante décadas cederán sin esfuerzo. La incógnita no es si ese día llegará, sino si habremos terminado de actualizar nuestras defensas a tiempo.