Informe Final

´ Indice general
1. Resumen 2. Introducci´n o 3. Marco Te´rico o 3.1. N´meros Primos . . . . . . . . . . . . . . . . . . . . . . . . . . u 2 3 6 6

3.2. Nociones sobre la hip´tesis de Riemann . . . . . . . . . . . . . . 20 o 3.3. Nociones sobre la hip´tesis extendida de Riemann . . . . . . . . 28 o 3.4. Curvas El´ ıpticas . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4. Mater´ ıalesy M´todos e 5. Resultados 37 38

5.1. Algoritmo de primalidad de Agrawal, Kayal y Saxena . . . . . . 40 5.2. El algoritmo de primalidad con curvas el´ ıpticas . . . . . . . . . 46 6. Discusi´n o 7. Referencias Bibliogr´ficas a 8. Apendice/Anexos 50 51 53

Cap´ ıtulo 1 Resumen
En el presente trabajo hacemos el estudio de dos algoritmos eficientes de primalidad, uno de ellos basado en teor´elemental de n´meros: el algoritmo ıa u AKS, manejable y accesible por la gran mayor´ y con las mejoras, ajustes y ıa contribuciones de Lenstra, Berstein y Berizbetia el algotritmo tiene un tiempo promedio de O(logn6 ), que lo hace eficiente; y el otro basado en la teor´ ıa de curvas el´ ıpticas, que aunque no es una teor´ sencilla, con ella se obtiene ıa resultados precisos de primalidad. Iniciamospresentando algunos conceptos y propiedades de los n´meros primos y hacemos de una breve explicaci´n de la u o hip´tesis de Riemann, uno de los siete problemas del milenio, que tiene coo mo premio un mill´n de d´lares ofrecido por el Clay Mathematical Institute. o o Establecemos la relaci´n de la hip´tesis de Riemman con las pruebas de prio o malidad, detallamos el algoritmo de Agrawal, Kayal ySaxena (AKS). Hacemos tambi´n un breve estudio de la teor´ curvas el´ e ıa ıpticas, para aplicarla a algoritmos de primalidad. El algoritmo usando curvas el´ ıpticas, aunque se basa en una teor´ con cierto grado de dificultad, pues usa una teor´ basada en algoıa ıa ritmos para determinar el n´meros de puntos de curvas el´ u ıpticas, en generar curvas de deterninado orden espec´ ıfico que sea apropiadoal problema a tratar, que no es tarea f´cil y es de investigaci´n actual, lo que lo hace poco accesible a o por las mayor´ es m´s preciso que el algoritmo AKS. Tanto el m´todo AKS ıas, a e como el m´todo de curvas el´ e ıpticas, tiene sus ventajas y sus desventajas; para optimizar los resultados es conveniente combinarlos para obtener resultados m´s eficientes. a

2

Cap´ ıtulo 2 Introducci´no
Desde los tiempos de Pit´goras los n´meros primos han sido objeto de a u estudio; de seguro, algunas de sus m´s elementales propiedades ya eran conoa cidas desde mucho tiempo antes. Probablemente las primeros en descubrirlos fueron las hombres del neol´ ıtico, que luego de recolectar alimentos para el grupo, debieron enfrentarse al problema de repartirlo; si la casualidad, o la mala suerteaparec´ y la colecta constaba de un n´mero primo de elementos, ıa u se habr´n dado cuenta de la imposibilitad de repartirlo de forma equitativa. a El inter´s que han suscitado los n´meros primos, ha sido muy variado; desde e u el inter´s puramente espiritual de los griegos (que los consideraban bello) e al que suscitaba durante el siglo XVIII-XIX como un problema matem´tico a “dif´ ıcil”. A lo largode la historia, han creado muchas formas y m´todos para tratar de e certificar que un n´mero es primo o no; a esto com´nmente se le denomina test u u de primalidad o simplemente PRIMES y es un ejemplo muy instructivo de como un mismo problema a ido cambiando su complejidad algor´ ıtmica a lo largo de los a˜os. n Actualmente, el inter´s por los primos, se debe al avance de la criptograf´ e ıa; puesel principal uso que se le est´ dando a los n´meros primos actualmente a u es el de generar claves criptogr´ficas, los m´todos criptogr´ficos actuales, usan a e a n´meros primos de muchas cifras , exageradamente grandes (llamados primos u industriales, t´ ıpicamente de 256 d´ ıgitos o bits ) como parte fundamental del proceso de encriptaci´n. Por lo que es fundamental tener algoritmos r´pidos o a...