Desde tiempos del genial Euclides se conoce que todo entero positivo puede ser factorizado en forma única como un producto de números primos, excepto por el orden de sus factores; esta propiedad es conocida como el “teorema fundamental de la aritmética”. En la actualidad, los sistemas de encriptación de datos ampliamente utilizados, tales como el sistema criptográfico “Rivest, Shamir, Adleman”, están basados en la siguiente conjetura: La factorización de enteros es mucho más difícil que su multiplicación. Mientras que la multiplicación de enteros se realiza en tiempo polinomial, no hay algoritmos clásicos de tiempo polinomial para su factorización. Esta suposición se encuentra fundamentada en el hecho de que, a pesar de los esfuerzos para encontrar un algoritmo de factorización de tiempo polinomial, no se ha tenido éxito hasta ahora. El algoritmo clásico más eficiente, para este propósito, conocido hasta la fecha es la “criba numérica de campo”. La criba numérica de campo es un algoritmo especializado de factorización en números primos. La frase “criba del cuerpo de números” se utiliza de manera equivalente a la criba general numérica de campo.
En teoría de números, el problema de la factorización de enteros consiste en encontrar un divisor no trivial de un número compuesto. Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema. Descomponer dos números de igual longitud no tiene por qué tener la misma complicación. Actualmente, a pocos meses de llegar a la primera década del siglo veintiuno, se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño. Por el “teorema fundamental de la aritmética”, cada entero positivo tiene una única descomposición en números primos. Dado un algoritmo para la factorización de enteros, se puede factorizar cualquier número entero a sus factores primos mediante la aplicación repetitiva de dicho algoritmo.
Los algoritmos de factorización se dividen en dos grupos claramente diferenciados: los de propósito general y los de propósito específico. El tiempo de ejecución de un algoritmo de factorización de propósito general depende solamente del tamaño del entero a factorizar. La mayoría de algoritmos de factorización de propósito general están basados en el método de congruencia de cuadrados. Algunos de los algoritmos de propósito general son los siguientes: (1) Algoritmo de Dixon, (2) Factorización con fracciones continuas. (3) Criba cuadrática. (4) Algoritmo general de criba de campos de números y (5) Factorización de formas cuadradas de Shanks. Por su parte el tiempo de ejecución de un algoritmo de factorización de propósito específico depende de las propiedades de sus factores desconocidos: tamaño, forma especial, etc. Dichos factores cambian de un algoritmo a otro. Algunos de los algoritmos de propósito específico general son los siguientes: (1) División por tentativa, (2) Algoritmo rho de Pollard, (3) Algoritmo p-1 de Pollard, (4) Algoritmo p+1 de Williams, (5) Factorización de curva elíptica de Lenstra, (6) Método de factorización de Fermat y (7) Algoritmo especial de criba numérica de campo.
El principal método para aumentar la capacidad de cálculo de una computadora clásica es el procesamiento en paralelo. Las computadoras que soportan este esquema de proceso disponen de varios cientos o miles de procesadores. Se conoce en el medio científico que la capacidad de almacenamiento de información y la capacidad de cálculo de una computadora son proporcionales al número de celdas de memoria y al número de procesadores respectivamente, es decir, al tamaño de la computadora. Entonces la capacidad de una computadora clásica, de almacenamiento y de cálculo, crece linealmente con respecto a su tamaño.
En una computadora cuántica la situación cambia por completo, hasta el punto que su capacidad crece exponencialmente con respecto a su tamaño. Este hecho, estrechamente relacionado con el principio de superposición de la mecánica cuántica, se denomina paralelismo cuántico. Se llama qbits o bits cuánticos a los sistemas cuánticos elementales, es decir, a los sistemas cuánticos de dos estados. Los sistemas cuánticos de varios qbits se describen mediante vectores de un espacio de Hilbert complejo de dimensión 2n. Esto permite codificar una cantidad exponencial de información en el estado de un sistema cuántico de varios qbits. Además, cualquier transformación del estado del sistema se traduce en la modificación simultánea de toda la información almacenada. Por tanto, la capacidad de una computadora cuántica crece exponencialmente con respecto a su tamaño. Sin embargo, la medición de estados cuánticos es un inconveniente importante para la computación cuántica. Hay que señalar que las medidas cuánticas no son deterministas. Esto quiere decir que si se miden dos estados iguales los resultados no tienen por qué ser iguales. El proceso de medida es, por tanto, un experimento aleatorio en el que la probabilidad de cada resultado está determinada por el estado del sistema.
Las dificultades para sacar provecho del paralelismo cuántico son tan notables que hubo que esperar más de una década para encontrar el primer gran resultado. El año 1994 Peter W. Shor, científico de los laboratorios AT&T Bell, sorprendió a todos presentando sendos algoritmos polinomiales para factorizar números enteros y para calcular logaritmos discretos. Fue el primer problema en el que se alcanzaba una aceleración exponencial con respecto a los mejores algoritmos clásicos conocidos. A raíz de este descubrimiento se generó una gran actividad, tanto en el desarrollo de la tecnología necesaria para la construcción de computadoras cuánticas como en el estudio de algoritmos cuánticos. La parte central del algoritmo de Shor es el algoritmo cuántico para encontrar el orden “ere minúscula” de un numero entero “equis minúscula” módulo un entero “ene mayúscula”, con “equis minúscula” menor que “ene mayúscula” y “equis minúscula” coprimo a “ene mayúscula”. El algoritmo de Shor para encontrar los factores primos de un número compuesto de varios cientos de dígitos, es bastante interesante porque prueba directamente que las computadoras cuánticas son mas poderosas que las clásicas y pueden ser utilizadas para romper las claves publicas del sistema criptográfico “Rivest, Shamir, Adleman” en tiempo polinomial.
El algoritmo de Shor rompió teóricamente el sistema criptográfico más difundido en la actualidad, el sistema propuesto por Rivest, Shamir y Adleman en 1978. Este hecho contribuyó a su vez al desarrollo de los sistemas criptográficos cuánticos. Las técnicas que se utilizan para garantizar la confidencialidad de los canales cuánticos se apoyan en una propiedad característica de la mecánica cuántica: los estados cuánticos no se pueden clonar. En el área de las comunicaciones, además del estudio de la confidencialidad, se están investigando otros problemas como, por ejemplo, la codificación de información clásica en canales cuánticos y el teletransporte de estados cuánticos. Sin embargo, el estudio de este modelo de computación apenas si ha comenzado. Hasta el momento, sólo se han desarrollado computadoras cuánticas basadas en resonancia magnética nuclear, en trampas de iones y en cavidades cuánticas. Con la primera de estas técnicas se han conseguido prototipos de hasta 10 qbits, sobre los que se ha probado el algoritmo de Shor. También se ha propuesto la construcción de computadoras cuánticas aprovechando los conocimientos actuales sobre semiconductores, aunque esta técnica está menos desarrollada.
Como señala Simon Singh en su excelente libro "The Code Book", a medida que la información se convierte en uno de los bienes más valiosos, el destino político, económico y militar de las naciones depende de la seguridad de los criptosistemas. Sin embargo, la construcción de una computadora cuántica acabaría con la privacidad, con el comercio electrónico y con la seguridad de las naciones. Una computadora cuántica haría zozobrar el ya frágil equilibrio mundial. De ahí la carrera de las principales naciones por llegar primero a su construcción. El ganador será capaz de espiar las comunicaciones de los ciudadanos, leer las mentes de sus rivales comerciales y enterarse de los planes de sus enemigos. La computación cuántica, todavía en mantillas, representa una de las mayores amenazas de la historia al individuo, a la industria y a la seguridad global.
En teoría de números, el problema de la factorización de enteros consiste en encontrar un divisor no trivial de un número compuesto. Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema. Descomponer dos números de igual longitud no tiene por qué tener la misma complicación. Actualmente, a pocos meses de llegar a la primera década del siglo veintiuno, se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño. Por el “teorema fundamental de la aritmética”, cada entero positivo tiene una única descomposición en números primos. Dado un algoritmo para la factorización de enteros, se puede factorizar cualquier número entero a sus factores primos mediante la aplicación repetitiva de dicho algoritmo.
Los algoritmos de factorización se dividen en dos grupos claramente diferenciados: los de propósito general y los de propósito específico. El tiempo de ejecución de un algoritmo de factorización de propósito general depende solamente del tamaño del entero a factorizar. La mayoría de algoritmos de factorización de propósito general están basados en el método de congruencia de cuadrados. Algunos de los algoritmos de propósito general son los siguientes: (1) Algoritmo de Dixon, (2) Factorización con fracciones continuas. (3) Criba cuadrática. (4) Algoritmo general de criba de campos de números y (5) Factorización de formas cuadradas de Shanks. Por su parte el tiempo de ejecución de un algoritmo de factorización de propósito específico depende de las propiedades de sus factores desconocidos: tamaño, forma especial, etc. Dichos factores cambian de un algoritmo a otro. Algunos de los algoritmos de propósito específico general son los siguientes: (1) División por tentativa, (2) Algoritmo rho de Pollard, (3) Algoritmo p-1 de Pollard, (4) Algoritmo p+1 de Williams, (5) Factorización de curva elíptica de Lenstra, (6) Método de factorización de Fermat y (7) Algoritmo especial de criba numérica de campo.
El principal método para aumentar la capacidad de cálculo de una computadora clásica es el procesamiento en paralelo. Las computadoras que soportan este esquema de proceso disponen de varios cientos o miles de procesadores. Se conoce en el medio científico que la capacidad de almacenamiento de información y la capacidad de cálculo de una computadora son proporcionales al número de celdas de memoria y al número de procesadores respectivamente, es decir, al tamaño de la computadora. Entonces la capacidad de una computadora clásica, de almacenamiento y de cálculo, crece linealmente con respecto a su tamaño.
En una computadora cuántica la situación cambia por completo, hasta el punto que su capacidad crece exponencialmente con respecto a su tamaño. Este hecho, estrechamente relacionado con el principio de superposición de la mecánica cuántica, se denomina paralelismo cuántico. Se llama qbits o bits cuánticos a los sistemas cuánticos elementales, es decir, a los sistemas cuánticos de dos estados. Los sistemas cuánticos de varios qbits se describen mediante vectores de un espacio de Hilbert complejo de dimensión 2n. Esto permite codificar una cantidad exponencial de información en el estado de un sistema cuántico de varios qbits. Además, cualquier transformación del estado del sistema se traduce en la modificación simultánea de toda la información almacenada. Por tanto, la capacidad de una computadora cuántica crece exponencialmente con respecto a su tamaño. Sin embargo, la medición de estados cuánticos es un inconveniente importante para la computación cuántica. Hay que señalar que las medidas cuánticas no son deterministas. Esto quiere decir que si se miden dos estados iguales los resultados no tienen por qué ser iguales. El proceso de medida es, por tanto, un experimento aleatorio en el que la probabilidad de cada resultado está determinada por el estado del sistema.
Las dificultades para sacar provecho del paralelismo cuántico son tan notables que hubo que esperar más de una década para encontrar el primer gran resultado. El año 1994 Peter W. Shor, científico de los laboratorios AT&T Bell, sorprendió a todos presentando sendos algoritmos polinomiales para factorizar números enteros y para calcular logaritmos discretos. Fue el primer problema en el que se alcanzaba una aceleración exponencial con respecto a los mejores algoritmos clásicos conocidos. A raíz de este descubrimiento se generó una gran actividad, tanto en el desarrollo de la tecnología necesaria para la construcción de computadoras cuánticas como en el estudio de algoritmos cuánticos. La parte central del algoritmo de Shor es el algoritmo cuántico para encontrar el orden “ere minúscula” de un numero entero “equis minúscula” módulo un entero “ene mayúscula”, con “equis minúscula” menor que “ene mayúscula” y “equis minúscula” coprimo a “ene mayúscula”. El algoritmo de Shor para encontrar los factores primos de un número compuesto de varios cientos de dígitos, es bastante interesante porque prueba directamente que las computadoras cuánticas son mas poderosas que las clásicas y pueden ser utilizadas para romper las claves publicas del sistema criptográfico “Rivest, Shamir, Adleman” en tiempo polinomial.
El algoritmo de Shor rompió teóricamente el sistema criptográfico más difundido en la actualidad, el sistema propuesto por Rivest, Shamir y Adleman en 1978. Este hecho contribuyó a su vez al desarrollo de los sistemas criptográficos cuánticos. Las técnicas que se utilizan para garantizar la confidencialidad de los canales cuánticos se apoyan en una propiedad característica de la mecánica cuántica: los estados cuánticos no se pueden clonar. En el área de las comunicaciones, además del estudio de la confidencialidad, se están investigando otros problemas como, por ejemplo, la codificación de información clásica en canales cuánticos y el teletransporte de estados cuánticos. Sin embargo, el estudio de este modelo de computación apenas si ha comenzado. Hasta el momento, sólo se han desarrollado computadoras cuánticas basadas en resonancia magnética nuclear, en trampas de iones y en cavidades cuánticas. Con la primera de estas técnicas se han conseguido prototipos de hasta 10 qbits, sobre los que se ha probado el algoritmo de Shor. También se ha propuesto la construcción de computadoras cuánticas aprovechando los conocimientos actuales sobre semiconductores, aunque esta técnica está menos desarrollada.
Como señala Simon Singh en su excelente libro "The Code Book", a medida que la información se convierte en uno de los bienes más valiosos, el destino político, económico y militar de las naciones depende de la seguridad de los criptosistemas. Sin embargo, la construcción de una computadora cuántica acabaría con la privacidad, con el comercio electrónico y con la seguridad de las naciones. Una computadora cuántica haría zozobrar el ya frágil equilibrio mundial. De ahí la carrera de las principales naciones por llegar primero a su construcción. El ganador será capaz de espiar las comunicaciones de los ciudadanos, leer las mentes de sus rivales comerciales y enterarse de los planes de sus enemigos. La computación cuántica, todavía en mantillas, representa una de las mayores amenazas de la historia al individuo, a la industria y a la seguridad global.
No hay comentarios:
Publicar un comentario