Definición: En 1994, Peter Shor, profesor de Matemáticas del MIT, ideó un algoritmo cuántico para generar factores primos de números grandes de forma mucho más eficiente que los ordenadores clásicos. El algoritmo de Shor es un algoritmo informático cuántico que puede resolver factores primos de un número entero en tiempo polinómico. Permite factorizar en números primos en tiempo O(logN ^3) y espacio O(logN).
Explicación del algoritmo de Shor
Encontrar factores primos ha sido un problema difícil durante siglos. El problema de la factorización es uno de los problemas no resueltos de la informática. Encontrar los factores primos de 51 puede llevar unos segundos, pero encontrar los factores primos de un número de 100 cifras puede llevar años utilizando varios ordenadores tradicionales que trabajen en paralelo.
Muchos algoritmos de cifrado utilizados para la seguridad de las tarjetas de crédito y otras transacciones financieras similares se benefician de este "problema de factorización". Se cree que si se puede resolver este problema de factorización, también se puede descifrar un algoritmo de cifrado como RSA. Un único ordenador cuántico podría resolver fácilmente este problema ejecutando el algoritmo de Shor.
El algoritmo de Shor sólo puede funcionar en ordenadores con un gran conjunto de bits cuánticos. En varios sistemas cuánticos, se han hecho muchos intentos de implementar el algoritmo de Shor; sin embargo, ninguno se ha acercado a implementarlo con unos pocos bits cuánticos. Se dice que el algoritmo de Shor es uno de los algoritmos de computación cuántica más difíciles conocidos hasta la fecha. El algoritmo puede realizarse en un ordenador cuántico.
Muchos esquemas de cifrado asumen que la factorización de grandes números es imposible en tiempo polinómico. Si fuera posible, algoritmos de cifrado como RSA podrían haberse roto. Esto está dando lugar al surgimiento de nuevos conceptos como la criptografía postcuántica y el hacking cuántico.
El algoritmo de Shor necesita 10.243 operaciones para factorizar un número de 1024 bits. Sin embargo, un ordenador cuántico que funcione a 100 MIPS puede factorizar un número de 1024 bits en segundos. Para conseguir un único estado entrelazado, funciona utilizando 2 registros, de tamaño 2048 y 1024 qubits respectivamente, que funcionan de forma coherente, para obtener un único estado entrelazado.
Problemas del algoritmo de Shor
- El Algoritmo de Shor no es el mejor método en ordenadores clásicos. Los algoritmos como Quadratic Sieve, Lenstra Elliptic Curve Factorization y General Number Field Sieve funcionan mejor para este problema en una máquina tradicional.
- A pesar del rendimiento increíblemente rápido del Algoritmo de Shor, el mayor número factorizado por un ordenador cuántico utilizando el Algoritmo de Shor es 21.
Aplicaciones del Algoritmo de Shor con un ordenador cuántico
- El algoritmo de Shor puede realizar la factorización de números primos muy grandes en un ordenador cuántico.
- El algoritmo de Shor puede utilizarse potencialmente para hackear RSA y otras formas de datos seguros
- El algoritmo de Shor puede resolver el problema de encontrar el periodo de una función.
Utimaco es capaz de proporcionar soluciones resistentes a los ordenadores cuánticos que permiten a las empresas defender sus sistemas contra ataques basados en ordenadores cuánticos gracias a importantes inversiones de tiempo y talento en criptografía post-cuántica.
