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)3) y espacio O(logN), así nombrado por Peter Shor.
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.
Muchas criptografías de clave pública, tales como RSA, llegarían a ser obsoletas si el algoritmo de Shor es implementado alguna vez en una computadora cuántica práctica.
Un mensaje cifrado con RSA puede ser descifrado descomponiendo en factores la llave pública N, que es el producto de dos números primos.
Los algoritmos clásicos conocidos no pueden hacer esto en tiempo O((log N)k) para ningún k, así que llegan a ser rápidamente poco prácticos a medida que se aumenta N. Por el contrario, el algoritmo de Shor puede romper RSA en tiempo polinómico.
También se ha ampliado para atacar muchas otras criptografías públicas.
El algoritmo de Shor fue aplicado en la práctica en 2001 por un grupo en IBM, que descompuso 15 en sus factores 3 y 5, usando una computadora cuántica con 7 qubits.
, es encontrar una solución para la ecuación: A la hora de intentar abordar este problema, existen un par de teoremas que son útiles: Sea
(De este último paso, esto es, hallar r, se encarga el circuito cuántico correspondiente).
[1] Este algoritmo sirve para factorizar números enteros de gran tamaño.
En todo momento, el algoritmo va a devolver un factor del número
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.
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
La siguiente fase, es implementar una comprobación para los números enteros
Esto se hace solo para comprobar si el número elegido comparte factores con
Estos algoritmos como se puede ver en los enlaces, dependen de la implementación del circuito cuántico en cuestión.
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.
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
Para el final del paso 3, tenemos un número entero a en este grupo.
Puesto que el grupo es finito, a debe tener un orden finito r, el número entero positivo más pequeño tal que Por lo tanto, N |(ar - 1).
N | uv, luego kN = uv para un cierto número entero k. Suponga que el mcd(u, N) = 1; entonces mu + nN = 1 para ciertos números enteros m y n (ésta es una propiedad del máximo común divisor).
Los físicos llaman a este comportamiento superposición cuántica.
Sin embargo, la física cuántica no permite que tengamos acceso a toda esta información directamente.
Esto es alcanzado usando la transformada de Fourier cuántica.
Shor tuvo que solucionar así tres "problemas de implementación".
Después de todas estas transformaciones una medición dará una aproximación al período r. Por simplicidad asuma que hay una y tal que yr/N es un número entero.
Por lo tanto la suma que nos da la probabilidad de la medición y será N/r puesto que b toma aproximadamente N/r valores y así la probabilidad es 1/r.
Hay r, y tales que yr/N es un número entero, luego la suma de las probabilidades es 1.