A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis.
Este artículo se refiere a un algoritmo de encriptado cuántico y uno de los primeros que se conocieron para computación o comunicación fotónicas. Los algoritmos de clave pública más populares hoy en día se refieren a tres problemas matemáticos: factorización de números enteros, el problema del logaritmo discreto y el problema de las curvas elípticas. Estos tres problemas se pueden resolver en un computador cuántico que ejecute el algoritmo que ha propuesto este autor. Su idea fue construir un algoritmo cuántico para generar factores primos de números grandes y de manera más eficiente que los ordenadores clásicos. Los aspectos clave del algoritmo son:1) es capaz de encontrar factores primos de un numero compuesto grande, 2) puede amenazar la seguridad de los sistemas actuales binarios como es el caso del RSA, 3) reduce la complejidad de exponencial a tiempo polinómico (término informático y de la teoría de la complejidad que describe la rapidez de un algoritmo en informática).
Especificaciones
- Autor/es: Peter Williston Shor.
- Fecha: 1994-11
- Publicado en: Proceedings 35th Annual Symposium on Foundations of Computer Science. Date of Conference: 20-22 November 1994.
- Idioma: Inglés
- Formato: PDF
- Contribución: José Antonio Delgado-Penín.
- Palabras clave: Inteligencia computacional y artificial, Matemáticas, Ordenadores y tratamiento de la información, Tecnologías cuánticas
