{"id":5629,"date":"2026-07-07T18:33:21","date_gmt":"2026-07-07T17:33:21","guid":{"rendered":"https:\/\/ccapitalia.net\/?p=5629"},"modified":"2026-07-08T08:40:08","modified_gmt":"2026-07-08T07:40:08","slug":"el-algoritmo-de-shor-y-la-factorizacion","status":"publish","type":"post","link":"https:\/\/ccapitalia.net\/?p=5629","title":{"rendered":"Algoritmo de Shor y factorizaci\u00f3n"},"content":{"rendered":"

Adolfo Garc\u00eda Yag\u00fce<\/a> | En mi profesi\u00f3n, 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\u00f3n o contrastar alguna informaci\u00f3n relevante, la exposici\u00f3n se queda en unos 45 minutos, de los que solo 40 son realmente \u00fatiles: peque\u00f1os retrasos, introducci\u00f3n de por qu\u00e9 estamos aqu\u00ed, etc.<\/p>\n

Siendo optimista, cuentas con 40 minutos para recorrer 26 diapositivas, lo que significa que dispones de apenas 1 minuto y medio por slide<\/em>. Es evidente que, en cuanto intentes profundizar en ciertos temas, consumir\u00e1s el tiempo en explicaciones en las probablemente quedar\u00e1s atrapado\u2026<\/p>\n

Esta introducci\u00f3n me permite hablar de la presentaci\u00f3n que compart\u00ed hace unas semanas sobre Computaci\u00f3n Cu\u00e1ntica y PQC<\/strong><\/a>. Aunque est\u00e1 siendo muy bien recibida y, desde que la liber\u00e9 en mayo, la he presentado ya en una docena de clientes con un feedback<\/em> satisfactorio, es una presentaci\u00f3n de elevado riesgo por su densidad conceptual y las ramificaciones hacia temas que suscitan numerosas preguntas\u2026 con el temido riesgo de hacer descarrilar cualquier planificaci\u00f3n de tiempos\u2026<\/p>\n

Aun as\u00ed, hasta el momento no se ha producido ninguna cat\u00e1strofe. Al contrario, cada exposici\u00f3n se ha convertido en un ejercicio de mejora continua que me permite afianzar conceptos que antes ten\u00eda algo difusos. Esa evoluci\u00f3n me ha llevado incluso a construir en Excel un sencillo modelo del Algoritmo de Shor<\/strong><\/a>, que me ha servido para entender con mayor precisi\u00f3n su funcionamiento y explicar sus fundamentos de forma m\u00e1s clara. Os lo dejo para que pod\u00e1is experimentar con \u00e9l; adem\u00e1s, me apoyar\u00e9 en este ejemplo para repasar paso a paso c\u00f3mo funciona el algoritmo.<\/p>\n

\"\"<\/a><\/p>\n

Cifrado de clave p\u00fablica RSA<\/strong>
\nPara este ejercicio he tomado como punto de partida el sistema de cifrado RSA (Rivest, Shamir y Adleman)<\/strong>, desarrollado en 1977 y todav\u00eda ampliamente utilizado. Recordemos que el elemento p\u00fablico m\u00e1s importante de RSA es el n\u00famero N<\/em><\/strong>, obtenido como el producto de dos n\u00fameros primos, p<\/strong><\/em> y q<\/em><\/strong>. Si un atacante consiguiera factorizar N<\/em><\/strong> y recuperar esos dos n\u00fameros primos, podr\u00eda reconstruir la clave privada.<\/p>\n

Aunque algunos pod\u00e9is pensar \u2014con raz\u00f3n\u2014 que RSA est\u00e1 siendo sustituido poco a poco por algoritmos basados en criptograf\u00eda de curva el\u00edptica (ECC, Elliptic Curve Cryptography)<\/strong>, ambos comparten la misma idea fundamental: su seguridad descansa en problemas matem\u00e1ticos que un ordenador cl\u00e1sico no puede resolver en un tiempo razonable.<\/p>\n

La ventaja de usar RSA como ejemplo est\u00e1 en que parte de su base matem\u00e1tica resulta m\u00e1s intuitiva que la de ECC. Al fin y al cabo, tod@s hemos trabajado con n\u00fameros primos en el colegio y, cuando llega el momento de aplicar Shor, no resulta confuso calcular un m\u00e1ximo com\u00fan divisor o construir una funci\u00f3n peri\u00f3dica. Como ver\u00e9is, estos conceptos se asimilan f\u00e1cilmente y permiten percibir la gravedad del problema con mayor claridad.<\/p>\n

Antes de seguir y as\u00ed evitar que alguien se frote las manos pensando que vamos a ense\u00f1ar a romper RSA con Shor, es importante recordar que nuestro ejercicio toma n\u00fameros muy peque\u00f1os de 2 y 3 cifras. Esto, en el mundo actual de la seguridad, es rid\u00edculo y cualquier n\u00famero empleado en RSA es superior a las 600 cifras (2048 bits) llegando incluso a superar las 1200 cifras (4096 bits).<\/strong><\/p>\n

Esto es as\u00ed porque, para un ordenador convencional, recuperar p<\/em><\/strong> y q<\/em><\/strong> a partir de un N<\/em><\/strong> lo suficientemente grande es computacionalmente inabordable. El m\u00e9todo b\u00e1sico de criptoan\u00e1lisis por fuerza bruta<\/strong> obligar\u00eda a buscar divisores de forma secuencial y, aunque se empleen algoritmos como General Number Field Sieve<\/strong> (GNFS)<\/strong>, el problema sigue siendo descomunal ya que romper un m\u00f3dulo RSA de 2048 bits contin\u00faa siendo una tarea computacionalmente inabordable con la tecnolog\u00eda actual.<\/p>\n

Algoritmo de Shor<\/strong>
\nEn 1994, el matem\u00e1tico Peter Shor (1959)<\/strong> demostr\u00f3 que la factorizaci\u00f3n de n\u00fameros no ten\u00eda por qu\u00e9 resolverse mediante \"\"una b\u00fasqueda exhaustiva. Su algoritmo transform\u00f3 el citado problema de factorizaci\u00f3n de N<\/em><\/strong> en el de hallar el per\u00edodo de una determinada funci\u00f3n. Para ello, el primer paso consiste en construir una funci\u00f3n a partir del n\u00famero N<\/em><\/strong> \u2014recordemos, el m\u00f3dulo p\u00fablico del sistema RSA\u2014 y estudiar su per\u00edodo.<\/p>\n

A primera vista puede parecer una idea extra\u00f1a. \u00bfQu\u00e9 tiene que ver el per\u00edodo de una funci\u00f3n con la factorizaci\u00f3n de un n\u00famero? Antes de responder a esa pregunta conviene olvidarnos por un momento de los ordenadores cu\u00e1nticos. De hecho, podemos comprender la idea utilizando \u00fanicamente la hoja de c\u00e1lculo adjunta<\/a>.<\/p>\n

El primer concepto que necesitamos conocer es la aritm\u00e9tica modular<\/strong>, tambi\u00e9n conocida como \u201cla matem\u00e1tica de los relojes\u201d. En un reloj, cuando pasan doce horas volvemos a empezar desde la una. No importa cu\u00e1ntas vueltas demos; el reloj siempre muestra un n\u00famero comprendido entre 1<\/strong><\/em> y 12<\/em><\/strong>.<\/p>\n

La aritm\u00e9tica modular funciona exactamente igual. Si trabajamos, por ejemplo, m\u00f3dulo 12<\/strong><\/em>, cualquier resultado que supere ese valor vuelve a empezar desde el principio. As\u00ed, 9 + 5 = 14<\/strong><\/em>, pero como 14<\/strong><\/em> deja un resto de 2<\/strong><\/em> al dividirlo entre 12<\/strong><\/em>, escribimos simplemente:<\/p>\n

14 mod 12 = 2<\/em><\/strong><\/p>\n

La criptograf\u00eda RSA utiliza precisamente este tipo de matem\u00e1ticas. En lugar de trabajar con n\u00fameros cada vez m\u00e1s grandes, realiza continuamente operaciones \u201cm\u00f3dulo N\u201d<\/strong>. Gracias a ello, aunque las cifras intermedias sean gigantescas, el resultado final siempre queda comprendido entre 0<\/em> <\/strong>y N \u2212 1<\/em><\/strong>.<\/p>\n

La funci\u00f3n que emple\u00f3 Shor es sorprendentemente sencilla:<\/p>\n

f(x) = a<\/em><\/strong>\u02e3 mod N<\/em><\/strong><\/p>\n

donde N<\/em><\/strong> es el m\u00f3dulo p\u00fablico de RSA y a<\/em><\/strong> es un n\u00famero entero elegido de forma que no comparta factores con N<\/em><\/strong>. Para comprobarlo utilizamos una operaci\u00f3n muy conocida en matem\u00e1ticas: el m\u00e1ximo com\u00fan divisor (MCD)<\/strong>, que indica cu\u00e1l es el mayor n\u00famero que divide exactamente a otros dos. Si el MCD de a<\/em><\/strong> y N<\/em><\/strong> es igual a 1<\/em><\/strong>, decimos que ambos n\u00fameros son coprimos<\/strong> y podemos continuar. Curiosamente, si el MCD fuese mayor que 1<\/em><\/strong>, habr\u00edamos encontrado directamente uno de los factores de N<\/em><\/strong>, resolviendo el problema incluso antes de empezar. Veamos un ejemplo muy sencillo:<\/p>\n

En nuestro ejemplo, supongamos que el m\u00f3dulo p\u00fablico es N = 15<\/em><\/strong> y elegimos a = 2<\/em><\/strong>. C<\/em>omo el MCD de 2<\/em><\/strong> y 15<\/em> <\/strong>es 1<\/em><\/strong>, podemos construir la funci\u00f3n y empezar a calcular sus valores (pod\u00e9is cambiar estos valores en la hoja hasta un m\u00e1ximo de N=101<\/strong><\/em>).<\/p>\n

<\/div>\n

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

Y aqu\u00ed aparece la idea brillante de Peter Shor. Ese n\u00famero, que a primera vista parece un simple dato m\u00e1s, contiene en realidad la informaci\u00f3n necesaria para recuperar los factores primos de N<\/em><\/strong>.<\/p>\n

Sin entrar en la demostraci\u00f3n matem\u00e1tica, basta saber que, cuando el per\u00edodo es par y se cumplen determinadas condiciones, tomamos el mismo valor de a<\/em> que elegimos al principio y lo elevamos a la mitad del per\u00edodo (r\/2)<\/em><\/strong>.<\/p>\n

En nuestro caso:<\/p>\n

r = 4\u00a0 \u00a0 \u00a0<\/em><\/strong>y\u00a0 \u00a0 a = 2<\/em><\/strong><\/p>\n

Por tanto:<\/p>\n

2 (4\/2) <\/sup>= 4<\/em><\/strong><\/p>\n

Nota: En este ejemplo ocurre una curiosidad ya que el per\u00edodo r<\/strong> vale 4<\/strong> y el c\u00e1lculo de a(r\/2)<\/sup><\/strong> tambi\u00e9n da como resultado 4.<\/strong> Es una simple coincidencia. En general, ambos valores no tienen por qu\u00e9 guardar ninguna relaci\u00f3n. <\/em>Dicho esto, a partir de ese resultado solo tenemos que realizar dos c\u00e1lculos utilizando el m\u00e1ximo com\u00fan divisor.<\/p>\n

Primero restamos una unidad:<\/p>\n

MCD(4 \u2212 1, 15) = 3<\/em><\/strong><\/p>\n

Despu\u00e9s sumamos una unidad:<\/p>\n

MCD(4 + 1, 15) = 5<\/em><\/strong><\/p>\n

Y, casi sin darnos cuenta, hemos recuperado los dos factores primos del n\u00famero:<\/p>\n

15 = 3 \u00d7 5<\/em><\/strong><\/p>\n

Una vez conocido el per\u00edodo, factorizar el n\u00famero deja de ser un problema complicado. La verdadera dificultad consiste en descubrir ese per\u00edodo cuando N<\/em><\/strong> tiene cientos o miles de bits, como ocurre en las claves RSA reales.<\/p>\n

Nuestra hoja de c\u00e1lculo reproduce el m\u00e9todo cl\u00e1sico: incrementa el valor de x<\/em><\/strong>, calcula a<\/em><\/strong>\u02e3 mod N<\/em><\/strong> y espera hasta que la secuencia empieza a repetirse. Con n\u00fameros peque\u00f1os funciona perfectamente, pero con una clave RSA real esa b\u00fasqueda puede resultar pr\u00e1cticamente inabordable.<\/p>\n

<\/p>\n

\u00bfC\u00f3mo evita ese problema un ordenador cu\u00e1ntico? La clave est\u00e1 en la Transformada Cu\u00e1ntica de Fourier (Quantum Fourier Transform o QFT)<\/strong>. Aunque su nombre resulte complejo, su funci\u00f3n es muy sencilla: poner de manifiesto la periodicidad de la funci\u00f3n<\/strong>.<\/p>\n

Una buena analog\u00eda es la m\u00fasica. Cuando escuchamos una orquesta percibimos una \u00fanica melod\u00eda, aunque en realidad est\u00e1 formada por muchos instrumentos. La transformada de Fourier act\u00faa como una herramienta capaz de separar esos sonidos y revelar el patr\u00f3n que hab\u00eda oculto. En el algoritmo de Shor hace algo parecido: utiliza la superposici\u00f3n cu\u00e1ntica para trabajar con muchos valores de x<\/em> simult\u00e1neamente y, mediante la Transformada Cu\u00e1ntica de Fourier, hace visible el per\u00edodo de la funci\u00f3n.<\/strong><\/p>\n

Esa es la aut\u00e9ntica revoluci\u00f3n del algoritmo de Shor. El ordenador cu\u00e1ntico no factoriza n\u00fameros por arte de magia ni calcula las potencias modulares mucho m\u00e1s deprisa; simplemente encuentra el per\u00edodo de la funci\u00f3n de una forma mucho m\u00e1s eficiente. Una vez conocido ese per\u00edodo, el resto del algoritmo vuelve a ser completamente cl\u00e1sico y permite obtener los factores primos mediante unas sencillas operaciones con el m\u00e1ximo com\u00fan divisor. Y precisamente por eso ha sido necesario desarrollar una nueva generaci\u00f3n de algoritmos PQC (Post-Quantum Cryptography)<\/strong><\/a> resistentes a este tipo de ataques.<\/p>\n

[Descargar hoja de c\u00e1lculo<\/a>]<\/p>\n","protected":false},"excerpt":{"rendered":"

Adolfo Garc\u00eda Yag\u00fce | En mi profesi\u00f3n, 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\u00f3n o contrastar alguna informaci\u00f3n relevante, la exposici\u00f3n se queda en unos 45 minutos, de los que solo 40 son realmente […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[654,814,146],"tags":[927,926,914,918],"class_list":["post-5629","post","type-post","status-publish","format-standard","hentry","category-academia","category-ciberseguridad","category-matematicas","tag-factorizacion","tag-peter-shor","tag-rsa","tag-shor"],"_links":{"self":[{"href":"https:\/\/ccapitalia.net\/index.php?rest_route=\/wp\/v2\/posts\/5629","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ccapitalia.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ccapitalia.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ccapitalia.net\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/ccapitalia.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5629"}],"version-history":[{"count":21,"href":"https:\/\/ccapitalia.net\/index.php?rest_route=\/wp\/v2\/posts\/5629\/revisions"}],"predecessor-version":[{"id":5652,"href":"https:\/\/ccapitalia.net\/index.php?rest_route=\/wp\/v2\/posts\/5629\/revisions\/5652"}],"wp:attachment":[{"href":"https:\/\/ccapitalia.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5629"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ccapitalia.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5629"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ccapitalia.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5629"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}