Un simulador cuántico facilita la factorización grandes números primos

Factorizar --expresar un número como el producto de otros números menores por los cuales este se puede dividir-- números muy grandes en sus principales "bloques de construcción" es extremadamente difícil para las computadoras clásicas, y esta dificultad subyace a la seguridad de muchos algoritmos criptográficos.

Si bien es fácil factorizar el número 20 como el producto de los números primos 2 x 2 x 5, por ejemplo, factorizar números más grandes se vuelve exponencialmente más difícil cuando se usan algoritmos de factorización clásicos.

En un nuevo artículo publicado en Physical Review A, los físicos José Luis Rosales y Vicente Martin, del Centro de Simulación Computacional de la UPM, han desarrollado un método que puede hacer mucho más fácil factorizar números muy grandes que se sabe que tienen exactamente dos factores primos.

El nuevo método determina la probabilidad de que cualquier número primo --aquel que sólo se divide por uno y por sí mismo-- sea uno de los dos factores primos de un número dado. Después de determinar estas probabilidades, los candidatos de factores primos más probables se pueden probar primero, lo que permite identificar los factores primos mucho más rápido que antes.

"La teoría muestra no solo dónde están ubicados los números primos, sino también la probabilidad de que un primo sea un factor de un número dado", dijo Rosales a Phys.org. "Por supuesto, esto tiene implicaciones en la criptografía porque (el criptosistema) RSA ignora esta regularidad".

Una de las cosas interesantes del nuevo método es que no utiliza ningún tipo de computadora, ya sea clásica o cuántica. En cambio, involucra un sistema cuántico físico, un "simulador cuántico", que, cuando se codifica con el número al factor, exhibe una distribución de probabilidad de valores de energía que es equivalente a la distribución de probabilidad de los candidatos del factor principal del número codificado.

Nueva teoria cuántia del problema de factorización

"Nuestro objetivo es desarrollar una nueva teoría cuántica del problema de factorización usando un simulador cuántico", dijo Rosales. "Nuestro enfoque ha descubierto una propiedad sin analogía clásica en teoría de números. Cada par de números primos que resuelven el problema se reorganizan para formar un patrón regular: el espectro de bandas del simulador cuántico".

La idea general detrás del simulador cuántico es algo llamado "conjunto de factorización", que los investigadores introdujeron anteriormente. Se basa en la idea de que los números primos se ordenan de menor a mayor (por ejemplo, 2 es el primer primo, 3 es el segundo primo y 101 es el primo 26). También es posible tomar la raíz cuadrada de cualquier número, y luego comparar el resultado con el primo más cercano. Por ejemplo, la raíz cuadrada de 27 es un poco más de 5, que es el tercer primo. Por la definición de un conjunto de factorización, esto significa que 27 pertenece al conjunto de factorización de 3.

Los físicos mostraron entonces que podían transformar la función del conjunto de factorización en una función de la física cuántica (la función de oscilador armónico invertido). Después de muchos más pasos, finalmente mostraron que el espectro de energía predicho de un sistema cuántico corresponde a la distribución de primos en el conjunto de factorización de un número. A partir de esta información, los investigadores pueden determinar la probabilidad de que un primo sea un factor de ese número. Para probar la validez de su método, los físicos probaron ciertos números y compararon sus resultados con las distribuciones reales obtenidas usando tablas de números primos, y encontraron distribuciones muy similares.

Los físicos demostraron teóricamente que el simulador cuántico propuesto puede factorizar números que son muchos órdenes de magnitud mayores que los que se han tenido en cuenta con las computadoras cuánticas. En su artículo, informan los resultados del uso de su método para determinar la distribución de probabilidad de los factores primos de un número con 24 dígitos. Además, el método hace esto con muchos menos recursos que los requeridos por los algoritmos de factoraje clásicos.

"En la teoría cuántica, la complejidad algorítmica es solo polinomial con la cantidad de bits del número que se debe factorizar", dijo Rosales.

Un último punto de interés es que el nuevo método tiene fuertes conexiones con la hipótesis de Riemann, que, de ser cierta, sugeriría que los números primos se distribuyen de manera predecible, de la misma manera que la distribución de los ceros de la función Riemann-zeta. Probar (o refutar) la hipótesis de Riemann es uno de los mayores problemas no resueltos en matemáticas, y uno de los problemas del Premio Milenio del Clay Mathematics Institute.

"Los primos deberían comportarse como números cuánticos si se aplica la conjetura de Hilbert-Polya", dijo Rosales, refiriéndose al viejo enfoque de probar la hipótesis de Riemann.

En el futuro, los investigadores están trabajando en la implementación experimental del simulador cuántico mediante el uso de dos partículas entrelazadas en una trampa Penning.

"El tratamiento completamente cuántico del simulador requeriría un análisis óptico cuántico de las interacciones de los fotones con dos (o más) iones enredados en una trampa Penning", dijo Rosales. "Esta parte del programa aún está en desarrollo. El objetivo es construir un simulador de factorización cuántica experimental. Si se implementa con éxito, los números de muchos órdenes de magnitud más grandes que los disponibles para su procesamiento cuántico utilizando el algoritmo de Shor se factorizarán y, como subproducto, la conjetura de Hilbert-Polya se probará experimentalmente".

Con información de Europa Press