Anterior | Inicio | Siguiente



Primalidad en Tiempo Polinomial: Una Introducción al Algoritmo AKS: Severino Collier Coutinho
Las décadas finales del siglo XX, y el inicio del siglo XXI, han sido marcados por progresos notables en la solución de problemas matemáticos importantes, algunos de los cuales estaban en abierto hace siglos. Esto es particularmente verdad en el caso de la teoría de números, con la solución de la Conjetura de Mordell por G. Faltings en 1984, y las demostraciones del ´Último Teorema de Fermat por A. Wiles, en 1995, y de la Conjetura de Catalan por P. Mihailescu, en el 2002. Sin embargo, la demostración de cada uno de estos resultados involucra una sección transversal importante de la matemática contemporánea, de modo que no son accesibles, salvo al especialista.
Esto explica el enorme impacto producido en la comunidad matemática por el descubrimiento de un algoritmo polinomial de primalidad por Agrawal, Kayal y Saxena. Ellos no solo resolvieron, de modo brillante, un problema que está con nosotros desde hace milenios, como que también la solución es tan simple que puede ser comprendida por un estudiante de pre-grado en matemática o ciencias de la computación. A decir verdad, la mayoría de las técnicas matemáticas usadas en el algoritmo, y en su demostración, ya eran conocidas desde el final del siglo XIX. Había solo dos excepciones: la noción de costo de un algoritmo, que solo fue formalizada en la segunda mitad del siglo XX, y un resultado sobre la distribución de primos en intervalos, publicada en 1985.
No asusta, por lo tanto, que la divulgación en la internet, en agosto de 2002, del artículo original de Agrawal, Kayal y Saxena haya provocado un frenesí raramente visto, que se difundió no solamente entre matemáticos y especialistas en computación, sino también entre todos los interesados en matemática, al punto de convertirse en noticia de periódico. Es claro que el uso de los primos en los sistemas de criptografía que garantizan la seguridad de nuestras transacciones por internet dio un brillo práctico a lo que sería, en otros tiempos, una curiosidad matemática. Para completar la atmósfera un poco mítica asociada a este tipo de hecho, los autores de la proeza eran tres hindúes, dos de los cuales recién habían acabado la carrera.
Pocas semanas después de la divulgación del artículo en la internet, estaba claro que el resultado era correcto, y comenzó la carrera para explotarlo, mejorarlo y generalizarlo. Es en este estado que estamos actualmente, y todavía es prematuro decir a qué nuevos algoritmos las ideas de Agrawal, Kayal y Saxena podrán conducir. Por otro lado, dos años después de descubierto, el algoritmo ya fue simplificado hasta el punto en que es posible describirlo de modo enteramente elemental, y es exactamente este nuestro objetivo. A decir verdad, el algoritmo expuesto en el capítulo 5 de este libro es una variación debida a H. W. Lenstra Jr del algoritmo que aparecieron en [Agrawal, Kayal y Saxena 2002]. La versión que presentamos sigue la exposición de D. Bernstein [Bernstein 2003], que a su vez incluye simplificaciones sugeridas por Kiran Kedlaya. La misión del libro es hacer que el algoritmo sea accesible, con todos sus detalles, a cualquiera que esté familiarizado con el contenido de [Coutinho 2003], o algún libro equivalente. Esto significa que, además de explicar todo el procedimiento del algoritmo, probamos que funciona correctamente y que tiene costo polinomial. Como siempre sucede, fue necesario pagar un precio para mantener el libro dentro de estos límites. Así, no fue posible formular el algoritmo de la manera más eficiente, ni llegar a obtener una estimativa precisa del costo. Además, el libro se concentra en la matemática que sirve de soporte al algoritmo, de modo que no abordamos en detalle cuestiones referentes a su implementación. Más informaciones sobre lo que quedó fuera del libro, incluyendo referencias sobre la implementación del algoritmo, se pueden encontrar en el epílogo.