Usuario:Emil1996/Taller

En computación cuántica, el algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O((log N)³) y espacio O(logN), así nombrado por Peter Shor.

El algoritmo de Shor es un procedimiento que permite encontrar factores de un número de una manera eficiente. La implementación de este algoritmo se puede llevar a cabo de manera clásica o utilizando circuitos cuánticos (que no han sido llevados a la práctica todavía). Esta última implementación es (por supuesto) la más conveniente cuando se desea encontrar el orden, un parámetro muy necesario a la hora de encontrar los factores primos de un cierto número. En todo este proceso se supondrá que ya se ha implementado un circuito cuántico para encontrar ese orden. ($r$ es conocido).

El problema de la factorización.

Sea $N\in \mathbb {N}$. Entonces, encontrar un factor $x\in \mathbb {N}$, es encontrar una solución para la ecuación:

$mod{(x^{2},N)}=1$

Es decir, se necesita encontrar un $x$ , tal que al dividir su cuadrado entre $N$ se tenga como resto 1.

A la hora de intentar abordar este problema, existen un par de teoremas que son útiles:

Teorema 1

Sea $N\in \mathbb {N}$, y sea $x$ una solución de la ecuación (*) (solución no trivial) donde es claro $1<x\leqslant N$. Entonces: Ó $m.c.d.{(x+1,N)}$ ó $m.c.d.{(x-1,N)}$ es un factor no trivial del número $N$.​

Teorema 2

Sea $N\in \mathbb {N}$ impar con descomposición en factores primos $N=p_{1}^{{\alpha }_{1}}\cdot ...\cdot p_{m}^{{\alpha }_{m}}$. Sea además $y\in \mathbb {N}$ (aleatorio) que es coprimo con $N$ ($1<y\leqslant N-1$) y $r$ el orden de ese número entero, es decir, aquel $r$ tal que: $mod{(y^{r},N)}=1$. ( De este último paso, esto es, hallar r, se encarga el circuito cuántico correspondiente). Entonces:

$Prob(r\,\,par\land mod(y^{\frac {r}{2}},N)\neq -1)\geq 1-{\biggl (}{\frac {1}{2}}{\biggr )}^{m}$

Con estos dos teoremas en mente, ya se puede empezar a plantear la secuencia en la que está basada el algoritmo de factorización de Shor.

Notas:

La notación que se utiliza es, en todo momento coherente, en el sentido de que las variables que aparecen en los teoremas y fuera de ellos o en cualquier otro contexto de a continuación son las mismas.

Por otro lado, la relación que presentan las variables $x$ e $y$ es:$\ y=x^{\frac {r}{2}}$. Como se va a poder ver en la siguiente sección.​

El algoritmo de Shor.

Este algoritmo sirve para factorizar números enteros de gran tamaño. Se exponen y se comentan todas las fases de este algoritmo. En todo momento, el algoritmo va a devolver un factor del número $\mathrm {N}$ que se desea descomponer. Los tres primeros casos corresponden a una implementación clásica, en el sentido de que no es necesaria la presencia de ningún circuito cuántico. Corresponden por tanto a la eliminación de casos de tipo trivial o que una implementación clásica puede realizar con suficientemente buena eficiencia.

1) Si N es par.

En efecto, la primera comprobación que se realiza al número es el caso trivial de que su última cifra sea un número par. En tal caso, el algoritmo devuelve 2, y el programa podrá continuar con ${\frac {N}{2}}$.

2) N es de la forma $a^{b}$.

La siguiente fase, es implementar una comprobación para los números enteros $a$ mayores o iguales a 1 y números $b$ mayores o iguales a 2. Se ha de tener en cuenta este tipo de números para que (como se verá en el paso 4) al utilizar el teorema 2 la probabilidad de obtener un buen candidato a factor sea más alta del 75%. En este caso, el algoritmo, devuelve el factor a.

3) Procedimiento aleatorio.

Se toma un número $y$ tal que $1<y\leqslant N-1$. Si $m.c.d.(y,N)>1$, entonces el programa devuelve precisamente este número. Esto se hace solo para comprobar si el número elegido comparte factores con $N$. En caso de que los dos números sean coprimos se sigue con el siguiente paso de la serie.

En este punto, dado el número natural $y$ anterior, se utilizan los algoritmos de estimación de fase y en concreto de orden, para hallar precisamente $r$ (el orden). Estos algoritmos como se puede ver en los enlaces, dependen de la implementación del circuito cuántico en cuestión.

4) Cálculo de $r$ y aplicación de los teoremas.

Como ya se dijo antes, partimos de que se conoce el orden. Ahora, se aplican los teoremas anteriores para intentar hallar este factor.

La primera parte de este último paso, consiste en la comprobación de si se cumplen los requisitos que el teorema 2 impone para asegurar una alta probabilidad. Esto ya se hizo en los procedimientos anteriores, pues se sabe que; $N$ es impar, tiene al menos dos factores primos distintos y es coprimo con $N$. Bajo estas condiciones, es posible asegurar que existe una alta probabilidad de que el número x sea no trivial, esto es: $mod(y^{\frac {r}{2}},N)\neq -1$

y que por supuesto $r$ es par.

Y habiendo comprobado esto, se está en disposición de aplicar el teorema 1 pues se cumplen a su vez todas las condiciones necesarias para poder aplicarlo y de esta forma obtener con alta probabilidad un factor de $N$. Bien $m.c.d.{(x+1,N)}$ ó $m.c.d.{(x-1,N)}$.

Como se ve todo este proceso depende de una cierta probabilidad de éxito. Si en algún punto el algoritmo falla, comienza de nuevo.​​​

Véase también

encontrar el orden para el algoritmo de Shor