Feb 07, 2024 | 9 min read
\( \newcommand{\bra}[1]{\langle #1|} \) \( \newcommand{\ket}[1]{|#1\rangle} \) \( \newcommand{\braket}[2]{\langle #1|#2\rangle} \) \( \newcommand{\i}{{\color{blue} i}} \) \( \newcommand{\Hil}{{\cal H}} \) \( \newcommand{\cg}[1]{{\rm C}#1} \) \( \newcommand{\lp}{\left(} \) \( \newcommand{\rp}{\right)} \) \( \newcommand{\lc}{\left[} \) \( \newcommand{\rc}{\right]} \) \( \newcommand{\lch}{\left\{} \) \( \newcommand{\rch}{\right\}} \) \( \newcommand{\Lp}{\Bigl(} \) \( \newcommand{\Rp}{\Bigr)} \) \( \newcommand{\Lc}{\Bigl[} \) \( \newcommand{\Rc}{\Bigr]} \) \( \newcommand{\Lch}{\Bigl\{} \) \( \newcommand{\Rch}{\Bigr\}} \) \( \newcommand{\rqa}{\quad \Rightarrow \quad} \)
1. Introducción#
1.1 - Criptografía y factorización#
El algoritmo de Shor es uno de los algoritmos de computación cuántica más conocidos debido a que es mejor en su tarea que cualquier algoritmo de computación clásica conocido hasta la fecha. Además, resuelve un problema que tiene una aplicación práctica directa: factorizar un número
Para entender porque este algoritmo es tan importante debemos hablar primero de criptografía, en concreto, del encriptado de transmisiones a través de Internet mediante el método de clave pública y clave privada (criptografía asimétrica). La explicación conceptual de esta forma de encriptar es simple. Cuando quieres, por ejemplo, acceder a la aplicación de tú banco tienes que ingresar las claves de acceso (DNI y pin), estas se mandan por Internet hasta la sede de tu banco, el cual verifica que son correctas y te da acceso. El problema radica precisamente en que la conexión se hace mediante Internet, con lo cual el mensaje con las claves de acceso puede ser interceptado. La solución a este problema es que el mensaje que el cliente envía esté encriptado y que solo tu banco pueda desencriptar el mensaje.
El método de encriptación más usado en Internet es la ya mencionada criptografía asimétrica. En este tipo de encriptado el receptor del mensaje (en nuestro ejemplo, el banco) genera dos claves dependientes entre sí, una la publicará al exterior (clave pública) y otra solo la conocerá él (clave privada). Si un receptor quisiera recibir un mensaje encriptado, bastaría con que publicase su clave pública de forma que cualquiera que quiera mandarle un mensaje, pueda usarla para encriptar el mismo. Sin embargo, la clave privada solo es conocida por el receptor del mensaje, y se usa para desencriptar. Puede decirse que la clave pública es como un candado y la clave privada es la llave. Cualquiera puede cerrar el candado, pero solo el que tiene la llave puede abrirlo. (Aquí podemos poner un poco más como se encripta/desencripta de forma sencilla…)
El punto importante aquí es que, la clave privada son dos números primos (de gran tamaño, cientos de cifras), y la clave pública es la multiplicación de estos dos números. La solidez de este método de cifrado (RSA) radica en el hecho de que si tenemos dos números primos multiplicarlos es muy fácil, pero si tenemos la multiplicación de los mismos (la clave pública) hallar cuales son los dos números con los que se construyó (factorizar el número en sus elementos primos) es extremadamente difícil. Como es esperable, cuanto más larga es la clave, más tiempo se tarda en factorizarla. El problema radica específicamente en que el tiempo que se requiere crece exponencialmente con el número de bits. Para las longitudes de clave que se manejan actualmente, incluso con los mejores superordenadores se tardarían cientos o miles de años en hallar los factores.
La tremenda potencia y aplicabilidad del algoritmo de Shor es que convierte este problema de complejidad exponencial en el número de bits para un computador clásico, en un problema de complejidad polinómica para un computador cuántico. Es decir, con el algoritmo de Shor el tiempo requerido para factorizar un número crece polinómicamente con el número de cifras del número. De esta forma, si se llega a tener un ordenador cuántico con suficientes qubits como para aplicar este algoritmo a números de la longitud de clave que se usa actualmente, se podrían factorizar y hallar la clave privada en un tiempo razonable para la escala humana. El algoritmo de Shor tiene el potencial de romper la criptografía asimétrica y hacer vulnerables las comunicaciones a través de la red, pero estamos muy lejos de tener un ordenador cuántico capar de implementarlo a la escala requerida. Se estima que se necesitarían del orden del millón de qubits, mientras que actualmente (año 2022) los ordenadores cuánticos más grandes andan por el orden de cientos de qubits.
1.2 - Algoritmo de factorización#
El algoritmo de Shor [14] se basa en el hecho de poder reducir un problema de factorización a uno de period (o order) finding (hallar el periodo -orden- de una función). Antes de hablar de nada cuántico, vamos a ver como sería la estructura general de un algoritmo de factorización de esta forma, tal y como se describe en el Nielsen-Chuang [9], comentando en que punto entra la computación cuántica para acelerarlo.
Lo primero es introducir la noción de números coprimos: dos números \(a\) y \(b\) son coprimos si su máximo común divisor es 1, esto es, gcd\((a,b) = 1\). Es decir, dos números coprimos solo comparten como divisor común el 1.
Los pasos reducir un problema de factorización en uno de period finding son los siguientes. Sea \(N\) el número que queremos factorizas
Si \(N\) es par, devolver el factor 2.
Determinar si \(N=p^b\) para los enteros \(p \geq 1\) y \(b \geq 2\), y si es así, devolver el factor \(p\) (puede hacerse en un tiempo polinómico).
Elegir un número entero aleatorio \(a\) tal que \(1 < a \leq N-1\). Usando el algoritmo de Euclides, determinar si gcd\((a,N) > 1\). Si lo es, devolver el factor gcd\((a,N)\).
Si gcd\((a,N) = 1\), calculamos el periodo \(r\) de la función \(f(x) = a^x \text{ mod} N\).
Si \(r\) es impar o \(r\) es par pero \(a^{r/2} \text{ mod} N =-1\), volvemos al paso 3. Sino, calculamos gcd\((a^{r/2}-1,N)\) y gcd\((a^{r/2}+1,N)\). Probamos a ver si uno de estos dos es un factor no-trivial de \(N\), y devolvemos el mismo si lo es.
Todos los pasos de este algoritmo, excepto el paso 4, se pueden implementar en un ordenador clásico y resolverse en un tiempo polinómico. Esto es debido a que para calcular el máximo común divisor puede usar el Algoritmo de Euclides [18], el cual resuelve el problema en un tiempo polinómico (se puede calcular en un tiempo razonable).
El paso complicado y que, por lo menos hasta la fecha, no hay ninguna forma de implementarlo en un tiempo polinómico (se implementa en un tiempo exponencial) en un ordenador clásico es el paso 4, hallar el periodo de la función. Sin embargo, este paso puede implementarse un ordenador cuántico en un tiempo polinómico. Tenemos pues que la forma óptima de factorizar un número consiste en implementar los pasos 1, 2, 3 y 5 en un ordenador clásico, y el paso 4 en un ordenador cuántico.
No vamos a comentar nada en este documento sobre los tres primeros pasos, pues no revisten mucha complejidad. Vamos a centrarnos en entender un poco el formalismos matemático detrás de los pasos 4 y 5, y en ver como podemos implementar el paso 4 en un ordenador cuántico.
1.3 - Explicación cualitativa.#
Vamos a intentar entender de forma cualitativa porqué calculando el periodo de una función se pueden hallar los factores de un número. En la sección 1.5 - Formalismo matemático. veremos un poco más en detalle las afirmaciones que se hacen en esta sección.
La función que nos interesa es la siguiente
donde \(a\) y \(N\) son enteros positivos mayores que 1, siendo además \(a\) < \(N\) y no teniendo factores comunes (es decir, cumpliéndose gcd\((a,N) = 1\)). La operación (\(z\) mod\(N\)) a lo que se refiere es a quedarnos con el resto de dividir el número que \(z\) por \(N\). Esta función se denomina exponenciales moduladas, se encaja dentro de la aritmética modular y si se cumplen las condiciones anteriores esta función es periódica. Denominaremos \(r\) al valor del periodo de la función \(f(x)\), es decir, \(r\) es el mínimo valor entero para que se cumple:
Este se puede calcular mediante un circuito cuántico.
Una vez se tiene el periodo \(r\), si este es par (sino hay que probar con otro valor de \(a\)) se pueden calcular los factores de \(N\). Esto es debido a que
con lo cual
Con lo cual, \(N\) debe ser un divisor de \(a^r-1\). Si \(r\) es par (sino hay que probar con otro valor de \(a\)), podemos escribir:
Entonces tenemos una alta probabilidad de que el máximo común divisor de \(N\) y \(a^{\,r/2}-1\) o \(a^{\,r/2}+1\) sea un factor propio de \(N\).
1.4 - Hallar el periodo en un ordenador cuántico.#
Como hemos comentado, el paso 4 descrito en la sección 1.2 - Algoritmo de factorización (buscar el periodo de \(f(x)\)) se puede implementar en un ordenador cuántico. Para ello lo que se hace es reducir el problema de la búsqueda de periodo a un problema de Estimación de Fase Cuántica (Quantum Phase Estimation) ([6] y [13]), que a su vez usa la Transformada de Fourier Cuántica (Quantum Fourier Transform) ([7] y [12]).
1.5 - Formalismo matemático.#
Veamos un poco el formalismo matemático detrás de las afirmaciones de la sección anterior.
1.5.1 - Periodicidad de \(f(x)\).#
Explicación aquí
Demostrar que, dada la condición gcd\((a,N) = 1\), la función \(f(x) = a^x \text{mod} N\) es periódica no es fácil, pues se necesitan plantear varios teoremas y la explicación se hace árida (puede verse el Appendix 4 del Nielsen-Chuang [9]). Aquí vamos a ver una explicación más simple partiendo del siguiente resultado (sin demostrarlos):
Dada la función \(f(x) = a^x \text{mod} N\), si se cumple que gcd\((a,N) = 1\), tenemos que para algún valor entero \(z>0\) se cumple \(f(z) = a^z \text{mod} N = 1\).
Vemos a ver ahora que este el menor valor \(z>0\) para el cual se cumple \(f(z) = a^z \text{mod} N = 1\) será el periodo de la función. Denominaremos a este valor \(r\), es decir, \(r\) será el primer valor (mayor que cero) para el cual se cumple \(f(r) = 1\). Tenemos que
En el momento en el que llegamos a un exponente \(r\) tal que \(a^r \text{ mod} N = 1\) podemos pues escribir
con lo cual
Hemos visto pues que \(f(x)\) es periódica.
1.5.2 - Factores de \(N\) a partir del periodo \(r\).#
Explicación aquí
Para entender como pasar del periodo \(r\) de nuestra función a tener los factores de \(N\) nos hace falta conocer un par de teoremas, ambos presentes en el Nielsen-Chuang [9].
Teorema: 5.2 del Nielsen-Chuang
Supongamos que \(N\) es un número compuesto de \(L\) bits, y \(x\) es una solución no trivial de la ecuación \(a^2 \text{ mod} N\) en el rango \(1 \leq a \leq N\), esto es, ni \(x \text{ mod} N = 1\) ni \(x \text{ mod} N = N-1 \text{ mod} N = -1 \text{ mod} N\). Entonces, uno de gcd\((x-1,N)\) y gcd\((x+1,N)\) es un factor no trivial de \(N\) que se puede calcular usando \(\mathcal{O}(L^3)\) operaciones.
Demostración
Ya que \(x^2 \text{ mod} N = 1 \rightarrow (x^2 -1) \text{ mod} N = 0\), debe de cumplirse que \(N\) divida a \((x^2-1) = (x+1)(x-1)\), con lo cual \(N\) debe de tener un factor común con \((x+1)\) o con \((x-1)\). Como por suposición tenemos que \(1 < x < N-1\), con lo cual \(x-1 < x+1 < N\), de lo cual podemos ver que el factor común no puede ser el propio \(N\). Usando el Algoritmo de Euclides podemos calcular gcd\((x-1)\) y gcd\((x+1)\), y con lo cual obtener un factor no trivial de \(N\), usando \(\mathcal{O}\) operaciones.
Teorema: 5.3 del Nielsen-Chuang
Supongamos \(N = p^{\alpha_1}_1 \dots p^{\alpha_m}_m \) es la descomposición en factores primos de un entero impar positivo. Sea \(x\) un número entero elegido uniformemente al azar, sujeto a la restricción \(1 \leq x \leq N-1\) y \(x\) coprimo de \(N\). Sea \(r\) el periodo de \(x \text{ mod} N\). Entonces
esto es, la probabilidad de hallar un \(r\) impar y que cumpla \(x^{r/2} \text{ mod} N = − 1) \geq 1\) es mayor que 1 − 1/\(2^m\).
Nota
En nuestro caso el teorema 5.2 se aplica con \(x = a^r\) y el teorema 5.3 con \(x = a\).
Los teoremas 5.2 y 5.3 pueden combinarse para dar un algoritmo que, con alta probabilidad, devuelve un factor no trivial de cualquier compuesto \(N\) . Todos los pasos del algoritmo pueden realizarse de forma eficiente en un ordenador clásico, excepto (por lo que se sabe hoy en día) una “subrutina” de búsqueda de periodo que utiliza el algoritmo. Repitiendo el procedimiento podemos encontrar una factorización prima completa de \(N\).
Autores:
David Castaño (UMA-SCBI), Raul Fuentes (BSC-CNS), Daniel Talaván (COMPUTAEX), Francisco Matanza (UNICAN)
License: Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
This work has been financially supported by the Ministry for Digital Transformation and of Civil Service of the Spanish Government through the QUANTUM ENIA project call - Quantum Spain project, and by the European Union through the Recovery, Transformation and Resilience Plan - NextGenerationEU within the framework of the Digital Spain 2026 Agenda.
