Posterior: Algoritmo cuántico para el Arriba: Algoritmo de Shor Anterior: Algoritmo de Shor

Pequeño recordatorio de Teoría de Números

Dados dos enteros $n,m$, su máximo común divisor es $d=\mbox{mcd}(n,m)$ tal que $d$ divide a ambos $n$ y $m$, es decir es un divisor común de $n$ y $m$, y cualquier otro divisor común divide a $d$ también. Se puede ver que $d$ es el menor entero positivo que se puede escribir como una combinación lineal de $n$ y $m$ con coeficientes enteros. El Algoritmo de Euclides calcula, para dos enteros $n$ y $m$ dados, $d=\mbox{mcd}(n,m)$ y lo expresa de la forma $d=an+bm$, con $a,b\in\mathbb{Z}$.

Los enteros $n$ y $m$ son primos relativos si $\mbox{mcd}(n,m)=1$, es decir, si no poseen un divisor común que no sea trivial. Sea $\Phi(n)=\{m\in[\![1,n]\!]\vert\, \mbox{mcd}(n,m)=1\}$ el conjunto de enteros positivos primos relativos con $n$, menores que $n$. Se tiene que el número de elementos en $\Phi(n)$ es el valor de la función de Euler $\phi$ en $n$. Con la multiplicación módulo $n$, $\Phi(n)$ es un grupo de orden $\phi(n)$. Así pues, si $m\in\Phi(n)$ entonces $m^{\phi(n)}=1\mbox{ mod }n$. Por tanto, para cada entero $m\in\Phi(n)$ existe un mínimo elemento $r$, divisor de $\phi(n)$, tal que $m^{r}=1\mbox{ mod }n$. Tal $r$ se dice ser el orden de $m$ en el grupo multiplicativo de residuos módulo $n$.

Sea $n$ un entero para el cual se ha de buscar un factor entero no trivial. Elijamos un entero $m$ tal que $1<m<n$. Si $\mbox{mcd}(n,m)=d>1$, entonces $d$ es un factor no-trivial de $n$. En otro caso, $\mbox{mcd}(n,m)=1$, y se tiene que $m$ quedará en el grupo multiplicativo de residuos de $n$, i.e. $m\in\Phi(n)$. Si acaso $m$ tuviera ahí un orden par $r$, entonces $k=m^{\frac{r}{2}}$ es tal que $k^2=1\mbox{ mod }n$. En consecuencia, $(k-1)(k+1)=0\mbox{ mod }n$, es decir $n$ divide al producto de dos números menores que él. Por tanto, los factores primos de $n$ han de aparecer como factores de esos números. Así pues al calcular $\mbox{mcd}(n,k-1)$ y $\mbox{mcd}(n,k+1)$ obtendremos factores no-triviales de $n$.

Un primer problema en este procedimiento de decisión consiste entonces en encontrar un elemento de orden par en el grupo multiplicativo de residuos módulo $n$. Si se elige $m$ al azar, la probabilidad de que $m$ sea de orden par es $1-\frac{1}{2^{\ell}}$ donde $\ell$ es el número de factores primos en $n$. Así pues, la probabilidad de que al cabo de $k$ intentos no se haya localizado un tal $m$ es $2^{-k\ell}$ y obviamente esto tiende a cero muy rápidamente al incrementar $k$. Así pues, bien vale la pena repetir pruebas arbitrarias de selección de un elemento (impar) menor que $n$ para localizar uno de orden par en el grupo multiplicativo de residuos módulo $n$.

Sin embargo, desde el punto de vista computacional, el mayor problema que presenta el algoritmo descrito radica en el cálculo del orden del elemento actual $m$ en $\Phi(n)$: el número de potencias de $m$ a calcular es del orden de $\phi(n)$ que a su vez es de orden $n$.

Sea $\nu=\lceil \log_2 n\rceil$ el número de bits necesarios para escribir a $n$, es decir, sea $\nu$ el tamaño de $n$. Resulta claro que $O(n)=O(2^{\nu})$ lo cual indica que el procedimiento anterior es de complejidad exponencial respecto al tamaño de la entrada. El algoritmo de Shor se fundamenta en un procedimiento polinomial en $\nu$ para realizar la tarea de calcular el orden de un elemento.

Posterior: Algoritmo cuántico para el Arriba: Algoritmo de Shor Anterior: Algoritmo de Shor