La factorización eficiente de números en sus factores primos constituye, desde hace ya muchas décadas, un desafío crucial en matemáticas y criptografía. El interés en este proceso, que se puede reducir a encontrar el período de una función periódica, viene de que los sistemas de encriptación más utilizados en el mundo digital descansan en la suposición (ampliamente aceptada pero no demostrada rigurosamente) de que es prácticamente imposible factorizar el producto de dos números primos grandes y desconocidos en un tiempo razonable. Esta dificultad es lo que hace que los códigos modernos sean seguros y prácticamente irreversibles. Calcular el producto de dos primos grandes es sencillo, pero determinar cuáles son esos números a partir del resultado es una tarea que, utilizando algoritmos clásicos y los ordenadores actuales, tomaría miles o millones de años.
Sin embargo, el nacimiento de la computación cuántica ha cambiado este panorama. Los ordenadores cuánticos no solo prometen resolver ciertos problemas de manera exponencialmente más rápida que las computadoras clásicas, sino que también tienen el potencial de romper los sistemas de encriptación actuales, como nos mostró por primera vez el algoritmo de Shor, presentado por Peter W. Shor en 1994. Este algoritmo aprovecha el fenómeno de las interferencias que se da en mecánica cuántica para factorizar números semiprimos de manera mucho más eficiente que cualquier algoritmo clásico.
El impacto de esta amenaza no es menor. Sistemas como RSA, que se basan en la dificultad de la factorización para garantizar la seguridad de datos financieros, comunicaciones y otros aspectos de la vida digital, podrían volverse vulnerables ante el poder de una computadora cuántica equipada con el algoritmo de Shor con la suficiente robustez y número de qubits.
Pero, ¿cómo es esto posible? En este post vamos a explicar de maneta pedagógica cómo funciona el algoritmo de Shor, lo vamos a hacer partiendo de la famosa radiografía del ADN de Rosalind Franklin.
La radiografía 51 es una figura de difracción. Se obtiene al enviar rayos X contra una estructura que se repite. En este caso, ADN cristalizado.
Las ondas electromagnéticas, cuando encuentran obstáculos, los bordean siguiendo distintos caminos. Como unos son más largos que otros, algunos llegan a la pantalla desfasados, como ese amigo pesado que, cuando estamos cansados y queremos irnos a casa, quiere seguir de fiesta.
En función de cómo sea el desfase, se obtiene interferencia constructiva en algunas zonas de la pantalla, y destructiva en otras.
Por ejemplo, en el caso de la rendija múltiple, lo que se obtiene es el patrón de máximos y mínimos siguiente:
La distancia entre dos máximos consecutivos es un ángulo. Este ángulo es proporcional a la longitud de onda de la luz. Pero, al ser un ángulo, no puede tener unidades de metros. En la fórmula tiene que aparecer otra distancia dividiendo.
Esa distancia b es el periodo del obstáculo o, mejor dicho, la distancia entre obstáculo y obstáculo (o entre agujero y agujero, ya que sale una figura del mismo tipo).
La distancia entre máximos consecutivos es inversamente proporcional al periodo que hay en la estructura cristalina que difracta los rayos X. Por eso, gracias a esta radiografía, no sólo podemos saber la forma del ADN, sino también las distancias que hay entre sus partes.
Por ejemplo, la distancia entre las líneas pequeñas que forman la cruz en forma de X en la radiografía de Franklin es inversamente proporcional a los 3,4 nm del periodo de la hélice. Matemáticamente se dice que es la transformada de Fourier. Así hallamos el periodo.
Uno de los ejemplos más sencillos en los que aparecen estructuras periódicas en matemáticas es en la aritmética modular. Por ejemplo, llamamos congruencias módulo 4 a las clases de equivalencia entre los años en los que hay olimpiadas o mundial de fútbol:
Así, el año 2023 fue congruente con 3 módulo 4. No hubo olimpiadas, pero sí Mundial de Fútbol Femenino.
Ahora vamos a jugar a un juego. Intenta factorizar el número 31007, es decir, escríbelo como un producto de números primos. Si en 2 minutos no lo has conseguido, sigue leyendo este artículo.
Multiplica 307 por 101. ¿A que esto si eres capaz de hacerlo en menos de 2 minutos? La seguridad del sistema criptográfico RSA, el más utilizado en el mundo, depende de que no podamos factorizar números muy grandes en un tiempo razonable.
Pero los ordenadores cuánticos potencialmente sí podrían factorizar números grandes muy rápido. Voy a intentar explicarlo con un ejemplo sencillo. Imaginemos que queremos factorizar el número:
Que no, es broma. Para explicarlo y que se entienda lo voy a hacer con el número 15. Cogemos un número pequeño al azar, por ejemplo el 2, y vamos haciendo potencias de este número módulo 15, es decir, módulo el número que queremos factorizar.
Se ve que el patrón se repite cada 4 porque 2^4 es 16, que es congruente con 1. Con ese dato de que el periodo es 4, se pueden encontrar rápidamente los factores de 15. Haciendo lo siguiente (si hubiera salido impar hay que repetir de nuevo el proceso).
Es decir, podemos reducir rápidamente el problema de factorizar un número N a encontrar el periodo de la función 2 elevado a x (módulo N). Pero, cómo podemos encontrar rápidamente el periodo de algo? Pues igual que se hace con el ADN, ¡con la difracción!
Esto en un ordenador cuántico se tiene que hacer con qubits. Se utilizan unas puertas lógicas que realizan una implementación cuántica de una transformada de Fourier discreta, pero la física cuántica involucrada aquí es básicamente la de la difracción por rendija múltiple.
Con una transformada de Fourier se consigue una superposición de M números, con M grande, se les aplica la función 2^x, y luego con otra transformada de Fourier cuántica (QFT) se consiguen interferencias constructivas en números cuya distancia es inversa al periodo de la función
Por ejemplo, para factorizar 15, la primera QFT nos da la superposición de la 1° línea. Al aplicar la función 2^x tenemos el entrelazamiento de la segunda línea. Si hacemos una medición en los qubits que dan el resultad de 2^x obtenemos la tercera línea colapsada.
En el algoritmo cuántico la medición anterior ni siquiera se hace. El entrelazamiento con los qbits que contienen 2^x ya garantiza que el sistema se comportará como si la función de onda hubiera colapsado, porque
el colapso no existe como proceso físico.
Luego aplicamos una segunda QFT a la 3° línea. Midiendo ahora (y repitiendo todo unas pocas veces) se obtienen resultados que difieren en múltiplos de una cantidad que es inversamente proporcional al periodo buscado. Así hayamos ese periodo, en este caso, 4.
El tiempo de computación con este algoritmo, que fue descubierto por
Peter Shor, crece de forma polinómica en el logaritmo del número a
factorizar. Los mejores algoritmos clásicos son muchísimo más lentos.
No obstante, no tenemos ahora mismo ordenadores cuánticos capaces de hacer esto con los numeros que se utilizan actualmente en criptografía. El problema principal para construir un ordenador cuántico que
implemente el algoritmo de Shor para factorizar las claves RSA actuales
es el
número de qubits que necesita.
La idea de reducir una factorización a encontrar el periodo de una función y usar la transformada de Fourier cuántica para hallarlo parece sencilla. Pero tuvieron que pasar muchas décadas desde el nacimiento de la mecánica cuántica para que a alguien se le ocurriera.
Sobre el autor: Sergio Montañez Naz es doctor en física teórica y profesor de secundaria de la enseñanza pública en la Comunidad de Madrid.
Referencias bibliográficas
- Galindo, A. y Martín-Delgado, M.A. (2001). Information and
Computation: Classical and Quantum Aspects. Recuperado el 19 de enero de
2014 de http://arxiv.org/pdf/quant-ph/0112105v1.pdf.
- Shor, P.W. (1994). Algorithms for quantum computation: Discrete log and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (STOC), 124-134. Recuperado el 19 de enero de 2014 de http://arxiv.org/abs/quant-ph/9508027.
No hay comentarios:
Publicar un comentario