GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

La seguridad de gran parte del mundo digital moderno descansa en un truco matemático simple: es increíblemente fácil multiplicar dos números primos grandes, pero es difícil averiguar qué dos números se utilizaron con solo mirar el resultado. Esta calle de sentido único es la base del cifrado RSA, el sistema que protege la banca en línea, los mensajes privados y las comunicaciones seguras. Durante décadas, la única forma conocida de romper este código era probar cada combinación posible de números hasta encontrar el par correcto, una tarea tan vasta que incluso las supercomputadoras más potentes tardarían más que la edad del universo en resolverla para claves grandes. Si bien las computadoras cuánticas prometen un día romper este código instantáneamente, aún no están listas para la tarea. Esto deja un vacío donde las computadoras clásicas deben encontrar una nueva forma de resolver el problema, no mediante la fuerza bruta, sino tratando la búsqueda de los números faltantes como un rompecabezas de energía y equilibrio.

Investigadores del Instituto Indio de Tecnología de Madras han desarrollado un nuevo método para abordar este desafío utilizando una unidad de procesamiento gráfico estándar, el tipo de chip que se encuentra en computadoras de alta gama para juegos y renderizado de video. En lugar de intentar adivinar los números directamente, transformaron el problema en un paisaje de colinas y valles, donde la solución se encuentra en el fondo mismo del valle más profundo. Mapearon los bits de los dos números primos ocultos en una cuadrícula de diminutos interruptores, cada uno de los cuales puede estar en uno de dos estados. El objetivo era encontrar la disposición específica de estos interruptores que crea el estado de energía más bajo, una configuración que codifica matemáticamente los dos factores primos correctos.

Para resolver esto, el equipo utilizó una técnica llamada recocido simulado (simulated annealing), que imita el proceso físico de enfriar el metal para eliminar defectos. En su versión digital, el sistema comienza con una disposición aleatoria de interruptores y un alto nivel de "calor", permitiendo que los interruptores cambien libremente. A medida que el sistema se enfría, los interruptores se asientan en un patrón más estable. Los investigadores diseñaron su software para ejecutarse en un solo chip gráfico potente, el NVIDIA GH200, que puede realizar miles de cálculos a la vez. Debido a que el mapa matemático que crearon está mayormente vacío —lo que significa que la mayoría de los interruptores no interactúan entre sí—, organizaron el trabajo para que la computadora se enfocara solo en las conexiones que realmente existían. Esto permitió actualizar muchos interruptores simultáneamente sin causar errores, una hazaña que requirió un método de clasificación ingenioso para asegurar que no dos interruptores que interactúan fueran cambiados en el mismo momento.

El sistema no siempre encontraba la respuesta perfecta de inmediato. En sus pruebas, el recocedor aterrizaba consistentemente muy cerca de la solución correcta, a menudo quedando a pocos porcentos de los números reales. Para cerrar este último vacío, los investigadores añadieron un segundo paso: una búsqueda guiada que verificaba números cercanos a la mejor suposición de la computadora. Utilizaron un método de filtrado para saltar sobre números que no podrían ser primos, reduciendo drásticamente el trabajo requerido. Para un número de 100 bits, todo el proceso, desde la configuración inicial hasta encontrar los factores finales, tomó poco más de seis minutos en una sola máquina. Esto es significativamente más rápido que los métodos tradicionales, que tomarían horas para la misma tarea.

Los investigadores probaron su flujo de trabajo en números que van desde los 16 hasta los 128 bits. Aunque lograron factorizar números de 100 bits en cuestión de minutos, señalaron que el método aún depende de un paso de búsqueda final para encontrar la respuesta exacta. La velocidad de este paso final depende en gran medida de qué tan cerca estuvo la suposición inicial de la verdad. El equipo encontró que su método consistentemente proporcionaba un punto de partida mucho mejor que las suposiciones más antiguas y simples, lo que redujo el tiempo necesario para la búsqueda final por un margen considerable. También demostraron que el uso de una técnica matemática específica conocida como el método de Coppersmith podría acelerar aún más el proceso para números más grandes, reduciendo potencialmente el tiempo de meses a días para números de 128 bits.

Este trabajo no rompe los estándares de cifrado actuales, ya que los números probados son mucho más pequeños que los utilizados en la seguridad del mundo real, que típicamente involucran números con cientos de dígitos. Sin embargo, demuestra que una computadora clásica, cuando es guiada por la estructura matemática adecuada y optimizada para el procesamiento paralelo, puede resolver este tipo de problema de manera mucho más eficiente de lo que se pensaba anteriormente. El estudio sugiere que el cuello de botella ya no es la velocidad bruta de la computadora, sino qué tan bien se puede refinar la suposición inicial. Si las mejoras futuras pueden acercar la computadora aún más a la solución, el paso de búsqueda final podría volverse tan pequeño que todo el proceso podría algún día ejecutarse en tiempo polinomial, una velocidad teórica que cambiaría el panorama de la criptografía. Por ahora, los investigadores han demostrado que al respetar la forma única del problema y utilizar el enorme poder de procesamiento paralelo de los chips gráficos modernos, es posible convertir un cerrojo matemático aparentemente imposible en un rompecabezas soluble.