¡Determinar Primos es Fácil!

Probablemente el resultado más importante en

teoría de la computación de los últimos 10 años

Shafi Goldwasser, MIT

Este mes seguimos con noticias de agosto. Unos días antes del deceso de Dijkstra y Nygaard, el 6 de agosto, tres investigadores indios del Instituto Tecnológico Indio en Kanpur, Manindra Agrawal, Neeraj Kayal y Nitin Saxena, publicaron en la Web (www.cse.iitk.ac.in/news/primality.html) un algoritmo de tiempo polinomial para determinar si un número era o no primo. Lo más sorprendente de la solución es que usa ideas relativamente simples de algebra y un resultado de teoría de números que ya tenía 15 años, presentando todo en sólo 9 páginas. El resultado ya ha sido verificado por conocidos investigadores del área y se piensa que es correcto.

Un Poco de Historia

Encontrar primos es un problema que ya tiene más de 2000 años, desde Eratóstenes y Euclides, y los primeros algoritmos necesitaban un tiempo exponencial. En los últimos 30 años muchos intentaron encontrar una solución obteniendo cuatro tipos de algoritmos distintos:

Algoritmos de tiempo polinomial basados en conjeturas matemáticas que se presumen ciertas, pero que nadie aún ha probado.
Algoritmos determinísticos casi de tiempo polinomial.
Algoritmos aleatorios de tiempo polinomial que tienen una pequeña probabilidad de equivocarse y decir que un número factorizable es primo.
Algoritmos aleatorios que no se equivocan, pero el tiempo es polinomial en promedio para casi todas las posibles entradas.

El nuevo algoritmo es determinístico y en el peor caso necesita un tiempo proporcional a n¹² donde n es el número de bits del número a determinar si es primo. En la práctica la mayoría de los algoritmos mencionados anteriormente son más rápidos que el nuevo, pero ya se ha reducido el exponente y se sabe que en promedio es mucho menor (a lo más 6).

La Criptografía (aún) está a Salvo

Una pregunta natural es que impacto tiene este resultado en la práctica, en particular en la criptografía. Por ahora, ningún impacto. Muchos algoritmos de encriptación ya usan algoritmos aleatorios para encontrar primos y su seguridad se basa en otro problema: que factorizar un número es difícil.

El problema de descomponer un número en sus factores primos todavía no se resuelve en forma eficiente y ni siquiera se sabe si puede tener una complejidad de tiempo polinomial. Si este problema fuera resuelto en forma eficiente, sin duda que sería posible violar la seguridad de algoritmos de encriptación famosos como RSA. Sin embargo, este nuevo algoritmo para determinar primalidad si puede dar nuevas ideas de como atacar el problema de la factorización.

Si tiene preguntas o sugerencias, envíe e-mail a rbaeza@dcc.uchile.cl