Algoritmo de Shor

Este información esta tomada a partir de la "supuesta" creación y fabricacioón de computadores cuanticos.

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.

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((logN)^k) para ningún k, así que llegan a ser rápidamente imprá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.

Como todos los algoritmos de computación cuántica, el algoritmo de Shor es probabilístico: da la respuesta correcta con alta probabilidad, y la probabilidad de fallo puede ser disminuida repitiendo el algoritmo.

El algoritmo de Shor fue demostrado en 2001 por un grupo en IBM, que descompuso 15 en sus factores 3 y 5, usando una computadora cuántica con 7 qubits.

El algoritmo se compone de dos partes. La primera parte del algoritmo convierte el problema de descomponer en factores en el problema de encontrar el período de una función, y se puede implentar clásicamente. La segunda parte encuentra el período usando la transformada de Fourier cuántica, y es responsable de la aceleración cuántica.

I. Obtención de factores a partir del período

Los números enteros menores que N y coprimos con N forman un grupo finito bajo multiplicación módulo N, que se denota típicamente (Z/N Z)^×. 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 |(a^r - 1). Suponga que podemos obtener r, y es par. Entonces

r es el número entero positivo más pequeño tal que a ^r ≡ 1, así que N no puede dividir a (a ^r/2 - 1). Si N tampoco divide (a^r/2 + 1), entonces N debe tener un factor común no trivial con (a^r/2 - 1) y (a ^r/2 + 1).

Prueba: Por simplicidad, denote (a^r/2 - 1) y (a^r/2 + 1) u y v respectivamente. 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.) Multiplicando ambos lados por v, encontramos que mkN + nvN = v, luego N |v. Por contradicción, mcd(u, N) ≠ 1. Por un argumento similar, mcd(v, N) ≠ 1.

Esto nos provee de una factorización de N. Si N es el producto de dos primos, esta es la única factorización posible.

fuente: wikipedia