Algoritmo de Shor y factorización

julio 7, 2026 on 6:33 pm | In academia, ciberseguridad, matemáticas | Comentarios desactivados en Algoritmo de Shor y factorización

Adolfo García Yagüe | En mi profesión, que un cliente dedique una hora de su tiempo a escucharte es un privilegio. Si de ese tiempo quieres reservar al menos 15 minutos para escuchar su opinión o contrastar alguna información relevante, la exposición se queda en unos 45 minutos, de los que solo 40 son realmente útiles: pequeños retrasos, introducción de por qué estamos aquí, etc.

Siendo optimista, cuentas con 40 minutos para recorrer 26 diapositivas, lo que significa que dispones de apenas 1 minuto y medio por slide. Es evidente que, en cuanto intentes profundizar en ciertos temas, consumirás el tiempo en explicaciones en las probablemente quedarás atrapado…

Esta introducción me permite hablar de la presentación que compartí hace unas semanas sobre Computación Cuántica y PQC. Aunque está siendo muy bien recibida y, desde que la liberé en mayo, la he presentado ya en una docena de clientes con un feedback satisfactorio, es una presentación de elevado riesgo por su densidad conceptual y las ramificaciones hacia temas que suscitan numerosas preguntas… con el temido riesgo de hacer descarrilar cualquier planificación de tiempos…

Aun así, hasta el momento no se ha producido ninguna catástrofe. Al contrario, cada exposición se ha convertido en un ejercicio de mejora continua que me permite afianzar conceptos que antes tenía algo difusos. Esa evolución me ha llevado incluso a construir en Excel un sencillo modelo del Algoritmo de Shor, que me ha servido para entender con mayor precisión su funcionamiento y explicar sus fundamentos de forma más clara. Os lo dejo para que podáis experimentar con él; además, me apoyaré en este ejemplo para repasar paso a paso cómo funciona el algoritmo.

Cifrado de clave pública RSA
Para este ejercicio he tomado como punto de partida el sistema de cifrado RSA (Rivest, Shamir y Adleman), desarrollado en 1977 y todavía ampliamente utilizado. Recordemos que el elemento público más importante de RSA es el número N, obtenido como el producto de dos números primos, p y q. Si un atacante consiguiera factorizar N y recuperar esos dos números primos, podría reconstruir la clave privada.

Aunque algunos podéis pensar —con razón— que RSA está siendo sustituido poco a poco por algoritmos basados en criptografía de curva elíptica (ECC, Elliptic Curve Cryptography), ambos comparten la misma idea fundamental: su seguridad descansa en problemas matemáticos que un ordenador clásico no puede resolver en un tiempo razonable.

La ventaja de usar RSA como ejemplo está en que parte de su base matemática resulta más intuitiva que la de ECC. Al fin y al cabo, tod@s hemos trabajado con números primos en el colegio y, cuando llega el momento de aplicar Shor, no resulta confuso calcular un máximo común divisor o construir una función periódica. Como veréis, estos conceptos se asimilan fácilmente y permiten percibir la gravedad del problema con mayor claridad.

Antes de seguir y así evitar que alguien se frote las manos pensando que vamos a enseñar a romper RSA con Shor, es importante recordar que nuestro ejercicio toma números muy pequeños de 2 y 3 cifras. Esto, en el mundo actual de la seguridad, es ridículo y cualquier número empleado en RSA es superior a las 600 cifras (2048 bits) llegando incluso a superar las 1200 cifras (4096 bits).

Esto es así porque, para un ordenador convencional, recuperar p y q a partir de un N lo suficientemente grande es computacionalmente inabordable. El método básico de criptoanálisis por fuerza bruta obligaría a buscar divisores de forma secuencial y, aunque se empleen algoritmos como General Number Field Sieve (GNFS), el problema sigue siendo descomunal ya que romper un módulo RSA de 2048 bits continúa siendo una tarea computacionalmente inabordable con la tecnología actual.

Algoritmo de Shor
En 1994, el matemático Peter Shor (1959) demostró que la factorización de números no tenía por qué resolverse mediante una búsqueda exhaustiva. Su algoritmo transformó el citado problema de factorización de N en el de hallar el período de una determinada función. Para ello, el primer paso consiste en construir una función a partir del número N —recordemos, el módulo público del sistema RSA— y estudiar su período.

A primera vista puede parecer una idea extraña. ¿Qué tiene que ver el período de una función con la factorización de un número? Antes de responder a esa pregunta conviene olvidarnos por un momento de los ordenadores cuánticos. De hecho, podemos comprender la idea utilizando únicamente la hoja de cálculo adjunta.

El primer concepto que necesitamos conocer es la aritmética modular, también conocida como “la matemática de los relojes”. En un reloj, cuando pasan doce horas volvemos a empezar desde la una. No importa cuántas vueltas demos; el reloj siempre muestra un número comprendido entre 1 y 12.

La aritmética modular funciona exactamente igual. Si trabajamos, por ejemplo, módulo 12, cualquier resultado que supere ese valor vuelve a empezar desde el principio. Así, 9 + 5 = 14, pero como 14 deja un resto de 2 al dividirlo entre 12, escribimos simplemente:

14 mod 12 = 2

La criptografía RSA utiliza precisamente este tipo de matemáticas. En lugar de trabajar con números cada vez más grandes, realiza continuamente operaciones “módulo N”. Gracias a ello, aunque las cifras intermedias sean gigantescas, el resultado final siempre queda comprendido entre 0 y N − 1.

La función que empleó Shor es sorprendentemente sencilla:

f(x) = aˣ mod N

donde N es el módulo público de RSA y a es un número entero elegido de forma que no comparta factores con N. Para comprobarlo utilizamos una operación muy conocida en matemáticas: el máximo común divisor (MCD), que indica cuál es el mayor número que divide exactamente a otros dos. Si el MCD de a y N es igual a 1, decimos que ambos números son coprimos y podemos continuar. Curiosamente, si el MCD fuese mayor que 1, habríamos encontrado directamente uno de los factores de N, resolviendo el problema incluso antes de empezar. Veamos un ejemplo muy sencillo:

En nuestro ejemplo, supongamos que el módulo público es N = 15 y elegimos a = 2. Como el MCD de 2 y 15 es 1, podemos construir la función y empezar a calcular sus valores (podéis cambiar estos valores en la hoja hasta un máximo de N=101).

En esta tabla lo interesante es el resultado de la segunda columna. Si nos fijamos, en ella observaremos un patrón que se repite 1, 2, 4, 8, 1, 2, 4, 8… La función ha entrado en un bucle. Decimos entonces que su período r es igual 4, porque cada cuatro valores la secuencia vuelve exactamente al mismo punto.

Y aquí aparece la idea brillante de Peter Shor. Ese número, que a primera vista parece un simple dato más, contiene en realidad la información necesaria para recuperar los factores primos de N.

Sin entrar en la demostración matemática, basta saber que, cuando el período es par y se cumplen determinadas condiciones, tomamos el mismo valor de a que elegimos al principio y lo elevamos a la mitad del período (r/2).

En nuestro caso:

r = 4     y    a = 2

Por tanto:

2 ^(4/2) = 4

Nota: En este ejemplo ocurre una curiosidad ya que el período r vale 4 y el cálculo de a^(r/2) también da como resultado 4. Es una simple coincidencia. En general, ambos valores no tienen por qué guardar ninguna relación. Dicho esto, a partir de ese resultado solo tenemos que realizar dos cálculos utilizando el máximo común divisor.

Primero restamos una unidad:

MCD(4 − 1, 15) = 3

Después sumamos una unidad:

MCD(4 + 1, 15) = 5

Y, casi sin darnos cuenta, hemos recuperado los dos factores primos del número:

15 = 3 × 5

Una vez conocido el período, factorizar el número deja de ser un problema complicado. La verdadera dificultad consiste en descubrir ese período cuando N tiene cientos o miles de bits, como ocurre en las claves RSA reales.

Nuestra hoja de cálculo reproduce el método clásico: incrementa el valor de x, calcula aˣ mod N y espera hasta que la secuencia empieza a repetirse. Con números pequeños funciona perfectamente, pero con una clave RSA real esa búsqueda puede resultar prácticamente inabordable.

¿Cómo evita ese problema un ordenador cuántico? La clave está en la Transformada Cuántica de Fourier (Quantum Fourier Transform o QFT). Aunque su nombre resulte complejo, su función es muy sencilla: poner de manifiesto la periodicidad de la función.

Una buena analogía es la música. Cuando escuchamos una orquesta percibimos una única melodía, aunque en realidad está formada por muchos instrumentos. La transformada de Fourier actúa como una herramienta capaz de separar esos sonidos y revelar el patrón que había oculto. En el algoritmo de Shor hace algo parecido: utiliza la superposición cuántica para trabajar con muchos valores de x simultáneamente y, mediante la Transformada Cuántica de Fourier, hace visible el período de la función.

Esa es la auténtica revolución del algoritmo de Shor. El ordenador cuántico no factoriza números por arte de magia ni calcula las potencias modulares mucho más deprisa; simplemente encuentra el período de la función de una forma mucho más eficiente. Una vez conocido ese período, el resto del algoritmo vuelve a ser completamente clásico y permite obtener los factores primos mediante unas sencillas operaciones con el máximo común divisor. Y precisamente por eso ha sido necesario desarrollar una nueva generación de algoritmos PQC (Post-Quantum Cryptography) resistentes a este tipo de ataques.

[Descargar hoja de cálculo]