Test de primalidad, el AKS Cruz Enrique Borges Hern´andez 7 de julio de 2005

Agradecimientos. Antes de comenzar el texto me gustar´ıa agradecer a mis compa˜ neros de clase, en especial a Rodrigo, por aguantar mis discursos y discusiones varias sobre los temas m´as absurdos imaginables y por sus sugerencias tanto a la hora de hacer el trabajo como en los quehaceres diarios del estudiante. Tambi´en deseo darle las gracias a los compa˜ neros “virtuales” del foro [76] por sus locuras y paranoias varias, pero sobre todo por volcarse cuando ped´ı ayuda a la hora de recopilar los datos para construir la gr´afica 1. As´ı como tambi´en darle las gracias a Javi, becario del departamento de Matem´aticas, Estad´ıstica y Computaci´on, que me permiti´o usar todos los ordenadores del aula del departamento y me puso todas las facilidades que pudo. En este punto considero importante darle las NO gracias al servicio de inform´atica de la Universidad de Cantabria, por las dificultades y trabas, al alumnado, para el uso de los todas las recursos y herramientas que la red nos pone a disposici´on. Especialmente en el Colegio Mayor Juan de la Cosa (aunque en las salas de inform´atica suceda algo parecido) lo que ha motivado que la realizaci´on de este trabajo sea much´ısimo m´as complicada de lo que debiera haber sido (aunque en el fondo deber´ıamos de estar agradecidos pues “al menos tenemos Internet”). Y desde aqu´ı tambi´en me gustar´ıa mostrar mi rechazo al cobro por la utilizaci´on de los recursos inform´aticos y bibliogr´aficos que se est´a comenzando a sugerir o en el caso de la biblioteca, a cobrar. Para finalizar darle las gracias a Luis por facilitarme much´ısimo material para realizar el trabajo y por aguantar mis depresiones cuando el trabajo no terminaba de coger forma. Y tambi´en a toda la comunidad de desarrolladores de herramientas GNU [77], en especial a los desarrolladores de MiKTeX [78], TeXnicCenter [79], Firefox [80] y Dev-C++ [59] que han sido las herramientas usadas principalmente para la realizaci´on de este trabajo.

1

Introducci´ on. Mi objetivo principal en este trabajo ha sido realizar un recorrido hist´orico por las llamadas clases centrales de la teor´ıa de complejidad algor´ıtmica comparando sus distintas propiedades tanto a nivel te´orico como pr´actico. Como excusa, o como pretexto, usaremos el bien conocido ejemplo (y realmente muy did´actico) de los test de primalidad. Comenzaremos realizando un recorrido hist´orico, bastante completo, sobre los distintos algoritmos usados para comprobar la primalidad. Empezaremos por los algoritmos griegos y ´arabes en el apartado 1.1, lo cual nos conduce a introducir la clase E. En el siguiente apartado trataremos los certificados de primalidad y composici´on cl´asicos, hablamos del certificado de Pratt y el test indeterminista de compositud. En este apartado nos introduciremos en el indeterminismo y la clase NP. Aunque no est´e relacionado directamente con dicha clase, tambi´en trataremos en este apartado otros algoritmos importantes y did´acticos. Por ejemplo, el test de Willson nos ilustra un algoritmo que a primera vista parece eficiente, pero del que actualmente no se sabe si lo es o no. Sin embargo, el polinomio de Matijasevic nos muestra algo completamente distinto, como caracterizar el conjunto de los n´ umeros primos mediante una f´ormula (con lo cual se demuestra que es un conjunto diof´antico). En el apartado 1.3 entraremos de lleno en el siglo XX y la algor´ıtmica moderna. Con el algoritmo de Solovay-Strassen introduciremos el important´ısimo concepto de los algoritmos aleatorios y la clase Co-RP. Hablaremos tambi´en del algoritmo de Miller-Rabin, hoy por hoy, el mejor y m´as r´apido test de primalidad (tanto es as´ı que es el test est´andar en pr´acticamente todos los paquetes inform´aticos). Posteriormente nos meteremos con los test en la clase RP basados en curvas el´ıpticas. Hablamos del ECPP y del APRCL. Para finalizar este apartado introduciremos el reciente test AKS y con ´el volvemos al determinismo y entramos en la clase P. A este algoritmo dedicaremos ´ıntegramente la secci´on 2. Comentaremos pormenorizadamente la demostraci´on de este algoritmo, su an´alisis de complejidad y las posibles mejoras que se han planteado. Para terminar esta primera parte, comentaremos en la secci´on 3 las implicaciones que trae el algoritmo en s´ı mismo, sobre todo lo referente a la seguridad inform´atica, criptograf´ıa y el criptosistema RSA. Tambi´en hablaremos, someramente, sobre las 2

nuevas v´ıas de investigaci´on en conjuntos cuestores y test de nulidad que ha abierto el algoritmo. En la segunda parte de trabajo comentaremos las diversas implementaciones del algoritmo que hemos desarrollado. Explicaremos con detalle los objetivos perseguidos y las dificultadas presentadas a lo largo de los diversos experimentos llevados a cabo. Para finalizar presentaremos un completo informe con las conclusiones obtenidas.

3

´Indice 1. El camino hasta P

5

1.1. PRIMES est´a en E . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2. PRIMES est´a en NP . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3. PRIMES est´a en Co-RP . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4. PRIMES est´a en RP . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2. PRIMES est´ a en P, el algoritmo AKS

23

2.1. El algoritmo y su correctitud . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. An´alisis de complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3. Algunas mejoras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3. Implicaciones del resultado

31

4. Implementaci´ on del algoritmo AKS

33

4.1. Implementaci´on en un paquete de c´alculo simb´olico . . . . . . . . . . 33 4.2. Implementaci´on con una librer´ıa de C++ . . . . . . . . . . . . . . . . 34 4.3. Experiencias realizadas . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3.1. Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3.2. Computaci´on GRID . . . . . . . . . . . . . . . . . . . . . . . 36 4.3.3. Prueba de estr´es al algoritmo de Miller-Rabin . . . . . . . . . 38 4.3.4. Verificaci´on de la conjetura 1.26 . . . . . . . . . . . . . . . . . 39 4.3.5. Prueba de estr´es al algoritmo de Miller-Rabin, otra vez . . . . 40 4.4. Conclusiones derivadas de la implementaci´on . . . . . . . . . . . . . . 40 A. Implementaci´ on del algoritmo en MAPLE

42

A.1. Implementaci´on alternativa del algoritmo en MAPLE . . . . . . . . . 44 B. Implementacion del algoritmo en C++ (bajo la libreria NTL)

46

B.1. B´ usqueda de errores en el algoritmo de Miller-Rabin . . . . . . . . . . 51 B.2. B´ usqueda de errores en conjetura 1.26

. . . . . . . . . . . . . . . . . 53

B.3. B´ usqueda de errores en el algoritmo de Miller-Rabin, revisi´on . . . . . 55 4

C. Script en MatLab para el dibujado de gr´ aficas

57

D. Resultados de la verificaci´ on de la conjetura 1.26

60

E. Estimaci´ on de la probabilidad de error en en algoritmo de MillerRabin 62 F. Ampliaci´ on del paquete listings perteneciente a LATEX 2ε

5

63

1.

El camino hasta P

Tenemos la certeza que desde los tiempo de Pit´agoras los n´ umeros primos han sido objeto de estudio, pero con total seguridad, algunas de sus m´as elementales propiedades ya eran conocidas desde mucho m´as antiguo. Probablemente las primeras en descubrirlas fueron las mujeres del Neol´ıtico, que tras recolectar alimentos para el grupo debieron enfrentarse al problema de repartirlo. Si la casualidad, o la mala suerte, aparec´ıa y la recolecta constaba de un n´ umero primo de elementos, r´apidamente se habr´an dado cuenta de la imposibilitad de repartirlo de forma equitativa, o sea de hallar un divisor. Otro ejemplo de la aparici´on de los n´ umeros primos se presenta en el ciclo vital1 de las cigarras Magicicada septendecim que es de 17 a˜ nos. Un n´ umero muy alto comparado con los dem´as miembros de su familia, aparte de ser un n´ umero primo. ¿Por qu´e la evoluci´on ha hecho que este tipo de cigarra tenga un ciclo vital tan largo y primo? La respuesta m´as plausible es la siguiente: Supongamos que la cigarra tiene un par´asito que tiene por ciclo vital n a˜ nos. A la cigarra le interesar´a evitar coincidir, en su fase adulta, con este par´asito, as´ı que la evoluci´on seleccionar´a aquellas cigarras cuyos ciclos vitales sean n´ umeros primo. Ahora bien, el par´asito tiene a´ un una oportunidad de sobrevivir, o adquiere un ciclo de un a˜ no o adquiere el mismo ciclo primo. Sin embargo para poder adaptarse a estos cambios el par´asito habr´a tenido que sobrevivir varias generaciones sin alimento, cosa altamente improbable, con lo cual se extinguir´a. . . o cambiar´a de alimentaci´on. Este hecho se avala en la certeza de no haberse encontrado nunca un par´asito de esta especie de cigarra. Una explicaci´on m´as detallada se puede encontrar en [7]. A lo largo del texto veremos los distintos m´etodos que han surgido a lo largo de la historia para certificar que un n´ umero es ciertamente primo. A este problema com´ unmente se le denomina test de primalidad o simplemente PRIMES y es un ejemplo muy instructivo sobre como un mismo problema a ido cambiando su complejidad algor´ıtmica a lo largo de los a˜ nos. El inter´es que han suscitado los n´ umeros primos ha sido muy variado. Desde el inter´es puramente “espiritual” de los griegos (que los consideraban “bello”) al que suscitaba durante el siglo XVIII-XIX como problema matem´atico duro. Podemos observar este hecho en las siguientes citas: 1

Periodo entre el nacimiento y el apareamiento. Por norma general, tras el apareamiento y la puesta de huevos este tipo de insectos muere.

6

Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate2 . Leonhard Euler. (1707 - 1783) Problema, numeros primos a compositis dignoscendi, hosque in factores suos primos resolvendi, ad gravissima ac utilissima totius arithmeticae pertinere [...] tam notum est, ut de hac re copiose loqui superfluum foret. [...] Praeteraeque scientiae dignitas requirere videtur, ut omnia subsidia ad solutionem problematis tan elegantis ac celebris sedulo excolantur3 . Carl Friedrich Gauss. (1777 - 1855) God may not play dice with the universe, but something strange is going on with the prime numbers4 . Paul Erdos. (1913 - 1996) Actualmente, el inter´es es debido a la criptograf´ıa. Los m´etodos criptogr´aficos actuales usan n´ umeros primos de muchas cifras decimales (llamados primos industriales) como parte fundamental del proceso de encriptaci´on. El mayor problema es que la seguridad del m´etodo se diluye cuando elegimos un n´ umero que creemos es primo cuando sin embargo no lo es. Por lo que es fundamental tener algoritmos r´apidos y eficientes que certifiquen la primalidad. Vamos a hablar un poco sobre lo que entendemos aqu´ı por rapidez y eficiencia de una forma muy simplificada e imprecisa5 . Ambos t´erminos est´an relacionados con la complejidad de un algoritmo, entendida la complejidad como el n´ umero de operaciones que realiza una m´aquina de Turing, “programada” con este algoritmo, hasta dar una respuesta. Esto es lo que entendemos por rapidez o complejidad en tiempo. O bien podemos considerar el tama˜ no m´aximo que toman las cintas de trabajo (memoria) que usa dicha m´aquina a lo largo de la ejecuci´on del algoritmo. Es lo que denominamos complejidad en espacio o eficiencia. 2

Los matem´ aticos han intentado, en vano hasta el momento, descubrir alg´ un orden en la secuencia de los n´ umeros primos y tenemos razones para creer que es un misterio en el cual la mente humana nunca podr´ a penetrar. 3 El problema de distinguir un n´ umero primo de otro compuesto y descomponer ´estos u ´ltimos en sus factores primos, es uno de los problemas mejor conocidos por su importancia y utilidad en aritm´etica, [...] sobra comentar la extensi´on de esta materia. [...] La dignidad de la ciencia requiere que todas las posibilidades sean exploradas para encontrar una soluci´on elegante y celebrada al problema. 4 Dios puede que no juegue a los dados con el universo, pero algo raro est´a haciendo con los n´ umeros primos. 5 Para una descripci´ on detallada de las clases de complejidad mirar [2] o [5]

7

Es claro que la complejidad variar´a en funci´on de la entrada que tenga el algoritmo. Intuitivamente se ve que a mayor entrada, es de esperar un mayor n´ umero de operaciones y/o memoria. En funci´on de las cotas que tengamos sobre las funciones de complejidad podemos clasificar los algoritmos en distintas clases, como por ejemplo: P, la clase de los algoritmos que tienen como cota una funci´on polinomial o NP la clase de los algoritmos indeterministas acotados por una funci´on polinomial.

1.1.

PRIMES est´ a en E

Ahora bien, pero. . . ¿qu´e es un n´ umero primo? La definici´on cl´asica o escolar que todos conocemos es algo as´ı: Definici´ on 1.1 (N´ umero primo). Sea n ∈ N. n es primo s´ı y s´olo s´ı los u ´nicos divisores que posee son 1 y n. Esta definici´on se generaliza para los dominios de integridad, lo cual da lugar al concepto de elemento primo. Definici´ on 1.2 (Elemento primo). Sea D un dominio de integridad y sea n ∈ D. n es un elemento primo si y solo si: a) n 6= 0 b) n no es una unidad. c) Si p divide a ab con a, b ∈ D entonces p|a o bien p|b. Nos enfrentamos ahora al problema en cuesti´on, ¿c´omo certificar que un n´ umero es primo? Si se le pregunta a un escolar lo m´as probable es que te conteste que miremos la tabla de n´ umero primos que tiene en su libro de textos (si es muy vago. . . o muy listo). O bien podr´ıa contestar que probemos a dividir por todos los n´ umeros menores que ´el (ahora bien, si es realmente listo dir´a que solo hace falta hasta su ra´ız cuadrada). Estas ideas simples fueron realmente los primeros test de primalidad. El primero es conocido como la criba de Erat´ostenes y es debido a Erat´ostenes (siglo II a.C.)6 . 6

Cuesta creer que Euclides, que muchos a˜ nos atr´as hab´ıa enunciado, y demostrado, el famoso

8

Algoritmo 1.3 (Criba de Erat´ostenes). Input = n ∈ Z Paso. 1 Escribir todos los n´ umeros hasta n. Paso. 2 Tachar el 1 pues es una unidad. Paso. 3 Repetir hasta n Tachar los m´ ultiplos del siguiente n´ umero sin tachar, excepto el mismo n´ umero. Output = Los n´ umeros tachados son compuestos y los no tachados son primos. Este algoritmo tiene la particularidad de que no s´olo nos certifica si un n´ umero es primo o no, sino que nos da todos los primos menores que ´el. El algoritmo funciona pues estamos comprobando si es o no m´ ultiplo de alg´ un n´ umero menor que ´el, lo cual es equivalente a la definici´on de numero primo. Este m´etodo es ´optimo cuando necesitamos construir la tabla con todos los n´ umeros primos hasta n, pero es tremendamente ineficiente para nuestro prop´osito, pues se trata de un algoritmo exponencial tanto en tiempo como en espacio. Sorprendentemente, no se tiene constancia del m´etodo trivial hasta el siglo XII cuando Leonardo de Pisa (m´as conocido como Fibonacci) introduce el m´etodo de las divisiones sucesivas, esto es, aplicar la definici´on tal cual. El algoritmo ser´ıa: Algoritmo 1.4 (Divisiones Sucesivas). Input = n ∈ Z Paso. 1 Mientras i
1. n es primo si y solo si (n − 1)! = −1 mod n. Demostraci´on. “⇐” El teorema es trivial para n = 2, 3 luego supongamos que n > 3. 9

Este m´etodo tambi´en es conocido como adition chain y puede encontrarse una explicaci´on completa en [4] o en [8].

12

Si n es un n´ umero compuesto ∃ a, b ∈ {1, . . . , n − 1} tales que n = ab con lo cual n divide a (n − 1)! y se cumple que (n − 1)! + 1 = 1 6= 0 mod n. “⇒” Si por el contrario n es primo se tiene que Zn es un cuerpo y por lo tanto ∀ x ∈ Zn \ {0} ∃| x−1 tal que xx−1 = 1 mod n. Adem´as x−1 6= x ⇔ x = 1, p − 1 con lo cual podemos formar parejas “n´ umero-opuesto” quedando de la siguiente forma: 2 · 3 · . . . · (p − 2) = (p − 2)! = 1 mod n ⇒ (p − 1)! = p − 1 = −1 mod n

El algoritmo que surge directamente de teorema es el siguiente: Algoritmo 1.11 (Test de Wilson). Input = n ∈ Z Paso. 1 Si (n − 1)! + 1 = 0 mod n entonces Output = Primo en otro caso Output = Compuesto Claramente se ve que es un algoritmo determinista que decide la primalidad de un elemento. Entonces. . . ¿d´onde est´a la trampa? El problema estriba en el c´alculo de (n−1)! Actualmente nadie conoce la forma de realizarlo eficientemente. Ni siquiera el caso modular (n−1)! mod n que evitar´ıa el crecimiento de los resultados intermedios. Cambiamos ahora un poco el contexto. Ahora en vez de buscar un algoritmo que nos certifique si un n´ umero es o no primo buscamos una funci´on que nos genere n´ umeros primos. Euler ya conoc´ıa que el polinomio x2 + x + 41 devuelve n´ umeros primos para x = 0, 1, . . . , 39. La pregunta que se hicieron los matem´aticos fue: ¿existe una funci´on la cual al evaluarla en los n´ umeros enteros devolviera los n´ umeros primos? Para desgracia de muchos la respuesta vino en forma de teorema: Teorema 1.12. Sea p(x1 , . . . , xn ) ∈ C[x1 , . . . , xn ] un polinomio multivariado con coeficientes complejos. Si p verifica que ∀ z ∈ Nn , p(z) es un n´ umero primo, entonces, p es constante (i.e. p ∈ C). La demostraci´on de este teorema, as´ı como informaci´on sobre la historia de su desarrollo se puede encontrar en [27] o en [28]. 13

Tras este peque˜ no traspi´es la investigaci´on no decay´o. Se relaj´o un poco las condiciones quedando ahora ¿existe un polinomio cuyos valores enteros positivos sea el conjunto de todos los n´ umeros primos? La respuesta a esta pregunta la trajo Matijasevic [24]. Teorema 1.13 (Polinomio de Matijasevic). El siguiente polinomio p ∈ Z[a, . . . , z]: (k + 2){1 − [wz + h + j − q]2 − [(gk + 2g + k + 1)(h + j) + h − z]2 − − [2n + p + q + z − e]2 − [16(k + 1)3 (k + 2)(n + 1)2 + 1 − f 2 ]2 − − [e3 (e + 2)(a + 1)2 + 1 − o2 ]2 − [(a2 − 1)y 2 + 1 − x2 ]2 − − [16r2 y 4 (a2 − 1) + 1 − u2 ]2 − − [((a + u2 (u2 − a))2 − 1)(n + 4dy)2 + 1 − (x + cu)2 ]2 − − [n + l + v − y]2 − [(a2 − 1)l2 + 1 − m2 ]2 − − [ai + k + 1 − l − i]2 − − [p + l(a − n − 1) + b(2an + 2a − n2 − 2n − 2) − m]2 − − [q + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2) − x]2 − − [z + pl(a − p) + t(2ap − p2 − 1) − pm]2 } verifica: {Y = p(a, . . . , z) ∈ Z : (a, . . . , z) ∈ Z26 , Y ≥ 0} = {n ∈ N : n es primo}. En otras palabras, los valores positivos de la imagen por p de los valores enteros son exactamente los n´ umeros primos positivos. Es un polinomio de 26 variables y grado 25 bastante poco manejable. Lo revolucionario de este teorema no es el hecho de que nos devuelva n´ umeros primos, sino el hecho de poder expresar, mediante un polinomio, una secuencia de n´ umeros recursivamente enumerable. Anteriormente a los resultados de Matijasevic [29] este problema fue estudiado por Julia Bowman Robinson a lo largo de su brillante carrera [30] y condujo a la resoluci´on del X problema de Hilbert [31].

1.3.

PRIMES est´ a en Co-RP

Dejamos ahora a un lado los algoritmos indeterministas y las curiosidades y veamos ahora el desarrollo de los algoritmos modernos 10 . Comenzaremos con una 10

Es de destacar que hasta mitades del siglo XX no se produjo ning´ un avance, pr´acticamente.

14

idea, bien simple, que nos servir´a de ejemplo. Hab´ıamos visto en el cap´ıtulo anterior que, por el teorema peque˜ no de Fermat, p ∀ a ∈ Z, a = a mod p. Bas´andonos en esto podr´ıamos construir el siguiente algoritmo: Algoritmo 1.14 (Test bruto de Fermat). Input = n ∈ Z Paso. 1 Desde a = 2 hasta n − 1 haz Si an−1 6= 1 mod n entonces Output = Compuesto. Paso. 2 Output = Probable Primo. El algoritmo es exponencial en tiempo, pues realizamos n pasos cada uno de O(log3 (n)) lo cual nos da un algoritmo de orden O(n log3 (n)). Adem´as, sabemos que cuando nos encontramos con un n´ umero de Carmichael, el algoritmo falla estrepitosamente. La definici´on de este conjunto de n´ umeros es: Definici´ on 1.15 (N´ umeros de Carmichael). n ∈ Z es un n´ umero de Carmichael si y s´olo si: a) n es compuesto. b) ∀x ∈ Z∗n on (x) es un divisor propio de n − 1. Una posible idea para mejorarlo podr´ıa ser: Algoritmo 1.16 (Test de Fermat). Input = n, k ∈ Z /* k = n´ umero m´aximo de repeticiones */ Paso. 1 Sea aux = i = 1 Paso. 2 Mientras (i ≤ k) y (aux = 1) Sea aux un n´ umero escogido aleatoriamente en {1, . . . , n − 1} aux = auxn−1 mod n i=i+1 15

Paso. 3 Si (aux = 1) entonces Output = Probable Primo. en otro caso Output = Compuesto. Ahora tenemos que s´olo hacemos a lo m´as k repeticiones con lo cual el algoritmo pasa a ser O(log3 (n)), a costa de poder equivocarnos en la respuesta. La probabilidad de error descender´a dependiendo del n´ umero de veces que repitamos el proceso, pero en el caso de toparnos con un n´ umero de Carmichael seguir´a fallando. Veamos a que clase pertenece: Para toda entrada es polinomial en tiempo. Si el input es primo entonces siempre devuelve primo. Si el input es compuesto entonces puede fallar. A primera vista puede parecer que pertenece a la clase Co-RP, pero debido a la existencia de los n´ umeros de Carmichael no pertenece a dicha clase (la probabilidad de error no esta acotada en dichos n´ umeros, siempre falla). Este primer ejemplo nos sirve de introducci´on a lo que ser´a lo com´ un a lo largo de este cap´ıtulo, los algoritmos probabilistas. Este tipo de algoritmos son muy r´apidos a costa de poder fallar “a veces”. Veamos ahora otro teorema que nos ve a permitir construir un algoritmo probabilista: Teorema 1.17. Sea n, a ∈ Z. n es primo ⇔ ∀ a ∈ {2, . . . , n − 1} se tiene que:   p−1 a = a 2 mod p. p Donde forma:

  a p

es el S´ımbolo de Legendre, que se puede calcular de la siguiente

0 si p divide a a. 1 si ∃ x tal que x2 = a mod n. -1 si 6 ∃ x tal que x2 = a mod n.

16

El teorema nos da una caracterizaci´on de los n´ umeros primos relativamente f´acil de calcular pero que es exponencial si queremos concluir primalidad. Sin embargo, en este caso no tenemos el handicap de los n´ umeros de Carmichael y realizando unas “pocas” pruebas podemos garantizar la primalidad con una probabilidad acotada. Veamos como quedar´ıa el algoritmo [37]: Algoritmo 1.18 (Test de Solovay-Strassen). Input = n, k ∈ Z /* k = n´ umero m´aximo de repeticiones */ Paso. 1 Desde i = 1 hasta k haz Sea a un n´ umero escogido aleatoriamente en {2, . . . , n − 1}
aux = na Si aux = 0 o a

p−1 2

− aux 6= 0 mod n entonces Output = Compuesto.

Paso. 2 Output = Probable Primo. Observamos que el algoritmo realiza O(kq) operaciones, donde q es el coste de calcular el s´ımbolo de Legendre. H. Cohen demuestra en [3] que el s´ımbolo de Legendre se puede calcular en no m´as de O(log2 (m)) con m = m´ax{a, n} con lo cual da lugar a un algoritmo de orden O(k log2 (n)) = O(log2 (n)). Adem´as, si definimos A = {a ∈ Z∗n tales que no se cumple el teorema cuando n no es primo} (conjunto de testigos) se puede ver que |A| > |Z∗n |/2. Veamos a que clase de complejidad pertenece: Para toda entrada es polinomial en tiempo. Si el input es primo entonces siempre devuelve primo. Si el input es compuesto la probabilidad de darlo por primo es menor que 1/2k . Con lo cual concluimos que este algoritmo pertenece a la clase Co-RP pues puede dar por primos n´ umeros que en realidad son compuestos11 . Este es el primer ejemplo que se propuso de algoritmo probabilista y se puede considerar a Solovay y Strassen como los padres de dichos algoritmos. 11

Notar que este es un algoritmo RP para el problema rec´ıproco, es decir, para decidir si un n´ umero es compuesto o no.

17

El mayor problema de este algoritmo radica en la dificultad para implementar el c´alculo del s´ımbolo de Legendre. Sin embargo a˜ nos m´as tarde aparecer´ıa otra caracterizaci´on de los n´ umeros primos que posibilitar´ıa un test sustancialmente mejor que ´este. La idea del test se la debemos a Miller y la posterior mejora a Rabin (que transform´o el algoritmo en probabilista usando las ideas de Solovay y Strassen). La idea detr´as del algoritmo es la siguiente. Sabemos que si n es primo, Zn es un cuerpo y por lo tanto x2 − 1 tiene exactamente dos ra´ıces, 1 y −1. Sin embargo esto no es cierto cuando n es compuesto, es m´as, se puede comprobar que podr´a tomar tantos valores distintos como dos elevado al n´ umero de factores primos que posea. Ahora bien, por el Teorema peque˜ no de Fermat sabemos que an−1 = 1 mod n, con n−1 lo cual a 2 es una ra´ız cuadrada de la unidad y por lo tanto s´olo puede ser 1 o −1. Repitiendo el proceso mientras tengamos factores pares, obtenemos una serie de valores que puede ser o bien {1, 1, . . . , 1} o bien {1, 1, . . . , −1}. A los n´ umeros con esta propiedad los podemos llamar testigos y se puede probar que m´as de la mitad de los enteros entre 1 y n cumplen dicha propiedad. Con lo cual probando con a = 1, 2, . . . , n/2 averiguar´ıamos si efectivamente n es primo o compuesto. A partir de este idea surge el siguiente algoritmo determinista que certifica primalidad [42]. Algoritmo 1.19 (Test determinista de Miller). Input = n ∈ Z Paso. 1 Escribir n − 1 = 2s d dividiendo sucesivas veces n − 1 entre 2. Paso. 2 Desde a = 2 hasta d2 log2 (n)e haz Si ad 6= 1 mod n entonces Output = Compuesto. Desde r = 0 hasta s − 1 haz r

• Si (a2 d ) 6= −1 mod n entonces Output = Compuesto. Paso. 3 entonces Output = Primo. La correctitud de este algoritmo est´a garantizada por la caracterizaci´on dada anteriormente de los n´ umeros primos, salvo por el peque˜ no detalle: s´olo comprobamos 2 los primeros 2 log (n) n´ umeros. Esto se debe a que este algoritmo fue dise˜ nado suponiendo cierta la siguiente conjetura (la cual nos permite acotar la distancia entre n´ umeros primos y nos da cierta una idea de su distribuci´on): 18

Conjetura 1.20 (Hip´otesis de Riemann). Definimos ζ(s) =

∞ X 1 con s ∈ C \ {1} funci´on zeta de Riemann. s n n=1

∀ s ∈ C \ {1, −2, −4, . . . , −2k} tales que ζ(s) = 0 ⇒ Re(s) = 1/2 La conjetura sigue estando sin es uno de los problemas abiertos Mathematics Institute ofrece una persona que demuestre el teorema

probar aunque es ampliamente aceptada12 . Este m´as importantes de las matem´aticas y el Clay recompensa de un mill´on de d´olares US$ a la [11].

Volviendo al algoritmo de Miller, la complejidad viene determinada por el bucle anidado. En el peor caso realizamos en el bucle externo 2 log2 (n) operaciones y en cada una de ellas O(log2 (n)) pues s es del orden O(log(n)) y mediante iterated squaring se tarda del orden O(log n) en realizar cada potencia. Obtenemos por tanto un algoritmo de orden O(log4 (n)). Ahora bien, supongamos que no nos creemos la hip´otesis de Riemann, Rabin [41] realiz´o una peque˜ na modificaci´on (usando las ideas de Solovay y Strassen como indicamos anteriormente) en el algoritmo para convertirlo en probabilista. El algoritmo quedar´ıa as´ı: Algoritmo 1.21 (Test Miller-Rabin). Input = n, k ∈ Z /* k = n´ umero m´aximo de repeticiones */ Paso. 1 Escribir n − 1 = 2s d dividiendo sucesivas veces n − 1 entre 2. Paso. 2 Desde i = 1 hasta k haz Sea a un n´ umero escogido aleatoriamente en {1, . . . , n − 1} Si ad 6= 1 mod n entonces Output = Compuesto. Desde r = 0 hasta s − 1 haz • Si a2

rd

6= −1 mod n entonces Output = Compuesto.

Paso. 3 Output = Probable Primo. 12

En el a˜ no 2004 Xavier Gourdon [17] verific´o num´ericamente la conjetura a lo largo de los primeros diez trillones de ceros no triviales de la funci´on.

19

El algoritmo es de orden O(k log2 (n)) = O(log2 (n)) como vimos anteriormente. Ahora bien, si definimos A = {a ∈ Z∗n tales que no se cumple el teorema cuando n no es primo} (conjunto de testigos) se puede demostrar que |A| > 3/4|Z∗n |. Con lo cual tenemos: Para toda entrada es polinomial en tiempo. Si el input es primo entonces siempre devuelve primo. Si el input es compuesto la probabilidad de darlo por primo es menor que 1/4k . Esto nos da un algoritmo en la clase Co-RP, como el caso de Solovay-Strassen, con la gran ventaja de no tener que calcular el s´ımbolo de Legendre y de tener el doble de testigos (con lo cual una probabilidad de error mucho menor). Actualmente este es el algoritmo implementado en la inmensa mayor´ıa de paquetes inform´aticos aunque en alg´ un caso se combina con otros test para bajar extremadamente la probabilidad de error [39]. Antes de continuar me gustar´ıa realizar un comentario hacerla de la probabilidad de error en estos algoritmos. Realizar 50 iteraciones del algoritmo de Miller-Rabin es algo plausible de llevar a cabo y tendr´ıamos que la probabilidad de errar ser´ıa 1/450 = 1/2100 una probabilidad muy inferior a la de que caiga un meteorito y destroce el laboratorio donde se est´a realizando el experimento. Pero es que incluso realizando “s´olo” 20 iteraciones tenemos que la probabilidad de error es 1/240 que es inferior a la probabilidad de que se produzca un error de hardware que produzca un error de c´alculo y haga fallar al algoritmo. Teniendo en cuenta estas afirmaciones se ve claramente que hay que tener muy mala suerte para que uno de estos algoritmos falle en la pr´actica.

1.4.

PRIMES est´ a en RP

La pregunta ahora es, ¿no existen algoritmos que certifiquen primalidad? O equivalentemente ¿no existen algoritmos en RP? La respuesta es que son tremendamente complejos, sin embargo vamos a hablar un poco sobre ellos. En 1980 Adleman, Pomerance y Rumely presentaron un algoritmo probabil´ıstico que certificaba primalidad. Posteriormente fue mejorado por H. W. Lenstra y H. Cohen en 1981. El resultado fue el conocido como APRCL, un algoritmo de orden O((log(n))c log(log(log(n))) ) para cierta constante c. Te´oricamente, el APRCL, es un 20

algoritmo exponencial aunque en la practica log(log(log(n))) se comporte como una constante para cualquier input que podamos considerar razonable13 . Existe tambi´en una versi´on determinista mucho m´as impracticable y una implementaci´on de ambos algoritmos, pero son ciertamente muy complejos de explicar (se basa en comprobar congruencias del estilo del Teorema peque˜ no de Fermat en cuerpos ciclot´omicos). Una descripci´on del algoritmo se encuentra en [3], [43], [44] y [45]. Por la misma ´epoca surge otro algoritmo te´orico (el ECPP) de la mano de Goldwasser y Kilian basado en curvas el´ıpticas. Fue modificado posteriormente por Atkin sobre la cual se realiza una implementaci´on (con Morain). El orden de este algoritmo es O(log6 (n)), pero no en el caso peor, sino en el caso medio (esto es, para casi todos los inputs es polinomial, pero existen algunos inputs para los que es exponencial). Posteriormente Adleman y Huang obtuvieron un test probabil´ıstico en tiempo polinomial (clase de complejidad RP) para el problema PRIMES aunque es totalmente impracticable. Una descripci´on de dichos test y de su implementaci´on se puede encontrar en [3], [48] y en la pagina web de F.Morain [46]. Las caracter´ısticas de este algoritmo son: Para toda entrada es polinomial en tiempo. Si el input es compuesto entonces siempre devuelve compuesto. Si el input es primo la probabilidad de darlo por compuesto es menor que 1/2k . Actualmente las certificaciones de primalidad se realizan con implementaciones y mejoras de este algoritmo. La idea aqu´ı es similar al algoritmo de Pratt, sustituyendo el grupo de n−1 elementos por el generado por una curva el´ıptica m´odulo n. Mientras tanto, el testigo pasa a ser un punto de la curva. La idea ahora es que el rango de valores del grupo es amplio y basta con ir probando con distintas curvas el´ıpticas hasta encontrar una que genere un grupo cuyo orden sepamos factorizar (con esto evitamos, en parte, el indeterminismo de factorizar n − 1 aunque generamos una b´ usqueda que puede ser muy compleja). Luego se aplica una idea similar al algoritmo de Pratt. T Como corolario obtenemos que PRIMES ∈ RP Co-RP = ZPP. Veamos una idea que nos permitir´ıa crear una implementaci´on realista y seria que nos garantizar´ıa la primalidad: 8

13

¡¡Y apara los no razonables tambi´en!! Para muestra un bot´on: log(log(log(1010 ))) ≈ 5. N´otese 9 que MAPLE produce un bonito mensaje de error (¡¡¡por number overflow !!!) si n = 1010 . . .

21

Algoritmo 1.22 (Test ZPP). Input = n ∈ Z Paso. 1 Correr el test de Miller-Rabin Paso. 2 Si Output = Probable Primo entonces correr el test ECPP // en otro caso Output = Compuesto. Paso. 3 Output = Output del test ECPP. Con este algoritmo obtenemos un test determinista de primalidad polinomial en media. Es decir, siempre vamos a obtener una respuesta correcta aunque en algunos casos tardemos mucho tiempo. Esto es as´ı pues si el n´ umero es compuesto y el algoritmo de Miller-Rabin devolviera probable primo el algoritmo ECPP s´olo podr´ıa devolver primo pues de devolver probable compuesto, de hecho, lo ser´ıa. En los dem´as casos no hab´ıa ninguna duda al respecto de la respuesta. Como hemos visto el camino hasta la certificaci´on de primalidad ha sido muy duro y en los u ´ltimos tiempos, enrevesado. Ha sido necesarios m´as de dos mil a˜ nos y el trabajo de muchas personas brillantes para solamente conseguir algoritmos probabilistas. Pero el panorama cambi´o el 8 de agosto de 2002. Manindra Agrawal, Nitin Saxena y Neeraj Kayal dan a conocer un borrador [50] (que aun se encuentra en ese estado, despu´es de su tercera revisi´on) en el que presentan un test de primalidad determinista en tiempo polinomial extremadamente simple. El algoritmo se basa en una generalizaci´on del Teorema peque˜ no de Fermat que con unos peque˜ nos arreglos permite construir un test en tiempo polinomial. Como la pr´oxima secci´on est´a dedicada ´ıntegramente a la explicaci´on de este algoritmo obviaremos los detalles por el momento. Aunque en sus primeras versiones usaba argumentos de teor´ıa anal´ıtica de n´ ume12 ros y el orden de complejidad era bastante alto (O(log (n))), gracias a las modificaciones de H. Lenstra y a A. Kalai, A. Sahai y M. Sudan incluidas en la segunda y tercera versiones del borrador, respectivamente, el algoritmo ofrece una prueba de la cota de complejidad O(log10,5 (n)) totalmente elemental14 , mientras que con un poco m´as de esfuerzo y algo de teor´ıa anal´ıtica de n´ umeros, se prueba la cota O(log7,5 (n)). 14

Por elemental se entiende a nivel de un alumno con un primer curso de ´algebra elemental cursado

22

Es de notar que bajo ciertas hip´otesis como la anteriormente mencionada hip´otesis de Riemann, la conjetura de Artin [14] o la conjetura de la densidad de los primos de Sophie-Germain [15] el algoritmo pasa a ser O(log6 n) sin realizar absolutamente ninguna modificaci´on15 . A partir de la idea revolucionaria que presentaron Agrawal y compa˜ n´ıa, primero Berrizbeitia [53], luego Qi Cheng [54] y por u ´ltimo Bernstein [55] presentaron16 sendas mejoras realizando h´ıbridos entre esta nueva idea y los test de curvas el´ıpticas ya existentes. El resultado es un test probabilista que certifica primalidad de orden O(log4 (n)) capaz de competir con el ECPP. Hay que comentar que si la siguiente conjetura es cierta, una peque˜ na modifica3 ci´on en el algoritmo reducir´ıa la complejidad del mismo a O(log (n)) ¡Sin perder el determinismo!. Conjetura 1.26. Si r es un n´ umero primo que no divide a n y (x − 1)n = xn − 1 mod (xr − 1, n) entonces o n es primo o n2 = 1 mod r. Actualmente comienzan a aparecer implementaciones de este algoritmo [57] que confirman los resultados te´oricos y es cuesti´on de tiempo que sea implementado por las principales librer´ıas de funciones y paquetes de c´alculo simb´olico. Veamos, a continuaci´on, con m´as detalle el algoritmo y su demostraci´on17 . 15

Dichas conjeturas aseguran:

Conjetura 1.23 (Conjetura de Artin). Dado n ∈ N tal que n 6= ab ∀ a, b ∈ N el n´ umero de primos n donde A(n) > 0, 35 q ≤ n para los cuales oq (n) = q − 1 se aproxima asint´ oticamente a A(n) ln(n) es la constante de Artin. Definici´ on 1.24 (Primos de Sophie-Germain). Se denomina primos de Sophie-Germain a las parejas de n´ umeros (n, 2n + 1) tales que ambos son n´ umeros primos. Conjetura 1.25 (Conjetura de la densidad de los primos de Sophie-Germain). Dado n ∈ N el 2C2 n n´ umero de primos q ≤ n de Sophie-Germain se aproxima asint´ oticamente a ln 2 (n) donde C2 ≈ 0, 66 es la constante de los primos gemelos [16]. 16

Notar que todos las citas anteriormente mencionadas est´an en fase de borrador y no han sido publicadas. 17 En los ap´endices se puede encontrar dos implementaciones del algoritmo original, una en MAPLE y otra en C++ as´ı como la modificaci´on propuesta para aplicar la conjetura 1.26

23

2.

PRIMES est´ a en P, el algoritmo AKS

2.1.

El algoritmo y su correctitud

Con anterioridad hemos estudiado muchos algoritmos que realizan un test de primalidad, desde la criba de Erat´ostenes hasta el AKS. Veamos con m´as detalle este u ´ltimo pues es un resultado muy importante al ser el primer algoritmo determinista en P que certifican primalidad. El algoritmo es bien simple y podr´ıa explicarse como “extra” al finalizar un primer curso de ´algebra abstracta. Se basa fundamentalmente en el siguiente resultado bien conocido desde hace mucho tiempo18 : Teorema 2.1 (Generalizaci´on del Teorema peque˜ no de Fermat). Sea a ∈ Z, n ∈ N, con (a, n) = 1 entonces n es primo si y solo si (x+a)n = xn +a mod n Demostraci´on. Por la f´ormula del binomio de Newton, sabemos que el coeficiente
que acompa˜ na a xi en el polinomio f (x) = (x + a)n − (x + a) es ni an−i
Si n es primo tenemos que ni = 0 pues es un m´ ultiplo de n. Si n es compuesto, sea q un primo tal que divida a n y sea k la mayor potencia de q que divida a n. Tenemos que:

k−1 q k no divide a nq pues si n = q k r nq = n(n−1)...(n−q) = q r(n−1)...(n−q) y como q! (q−1)! en el numerador no hay ning´ un m´ ultiplo de q obtenemos el resultado. (q k , an−q ) = 1 pues (n, a) = 1 Por lo que el coeficiente que acompa˜ na a xq 6= 0 y por lo tanto no se tiene que (x + a)n = xn + a mod n Con esto obtenemos una caracterizaci´on de los n´ umeros primos que podr´ıamos usar de forma algor´ıtmica. Pero surge un problema, el n´ umero de operaciones es exponencial, con lo cual hemos retrocedido bastante. Sin embargo vemos como podemos reducir el n´ umero de operaciones. Lo ideal ser´ıa que una afirmaci´on de este tipo fuera cierta: 18

El teorema generaliza el Teorema peque˜ no de Fermat

24

Conjetura 2.2. Sea a ∈ Z, n ∈ N y (a, n) = 1 entonces n es primo si y solo si (x + a)n = xn + a mod (xr−1 , n) donde r es suficientemente peque˜ no. Pero por desgracia la anterior propiedad es falsa. Bueno, m´as bien, no se da en general, existen n´ umeros compuesto que la cumplen. Ahora bien, no est´a todo perdido, veremos a continuaci´on que si se da la propiedad para un determinado r y un conjunto de a podemos recuperar la caracterizaci´on. B´asicamente esto es el algoritmo. El factor novedoso de este algoritmo est´a exactamente ah´ı, en la elecci´on de la r y las a. Es una idea novedosa y que previsiblemente servir´a de inspiraci´on para futuros algoritmos no necesariamente relacionados con los test de primalidad. Presentamos a continuaci´on el algoritmo original del AKS. M´as adelante comentaremos diversas modificaciones y posibles mejoras: Algoritmo 2.3 (AKS). Input = n ∈ Z Paso. 1 Si n = ab para alg´ un a ∈ N y b > 1 entonces Output = Compuesto. Paso. 2 Encuentra el menor r tal que or (n) > 4 log2 (n) Paso. 3 Si 1 < (a, n) < n para alg´ un a ≤ r entonces Output = Compuesto. Paso. 4 Si n ≤ r entonces Output = Primo. p Paso. 5 Desde a = 1 hasta b2 ϕ(r) log(n)c comprueba si (x + a)n 6= xn + a mod (xr − 1, n) entonces Output = Compuesto. Paso. 6 Output = Primo. Vamos a ver que efectivamente este algoritmo cumple su cometido y distingue n´ umeros primos de compuestos. Teorema 2.4. Si n es primo entonces el algoritmo devuelve Primo. Demostraci´on. Observamos que si n es primo tanto en el primer como en el tercer paso, el algoritmo no puede nunca devolver Compuesto. As´ı como, por el teorema 2.1, tenemos que el quinto paso tampoco devolver´a Compuesto. Por lo tanto el algoritmo devolver´a Primo o en el cuarto paso o en el sexto. 25

Para realizar el rec´ıproco de este teorema deberemos trabajas m´as. La idea es definir un conjunto de valores a partir de n y comprobar que generan un grupo c´ıclico que acotaremos. Ahora bien, si se cumple el paso quinto del algoritmo y suponemos que n es compuesto llegaremos a un absurdo, pues no se respetar´an las cotas prevista. Sin m´as vamos a desarrollar la teor´ıa. Veamos primero si existe un r con las propiedades pedidas en el segundo paso. Para ello usaremos el siguiente lema: Lema 2.5. lcm{1, . . . , k} ≥ 2k si k > 1 Demostraci´on. Sea dn = lcm{1, . . . , n} y consideramos para 1 ≤ m ≤ n la integral: Z

1

I = I(m, n) =

x

m−1

n−m

(1 − x)

dx =

0

n−m X

r

(−1)

r=0



 n−m 1 r m+r

Que resolvi´endola por partes obtenemos:

I=

1 m

n m




Tenemos entonces que: Idn ∈ N


n n n m m divide a dn pues Im m = 1 ⇒ dn Im m = dn y como dn I = q ∈ N
n tenemos que m m divide a dn para todo 1 ≤ m ≤ n.


2n 2n+1 En particular, n 2n divide a d y como (2n + 1) = (n + 1) tenemos 2n n n n+1

2n 2n entonces que (n+1) n y (2n+1) n dividen a d2n−1 Adem´as, como (n, 2n+1) = 1

2n obtenemos que n(2n + 1) 2n divide a d y por lo tanto d ≥ n(2n + 1) ≥ 2n+1 2n+1 n n P2n 2n
2n 2n 2n+1 N n i=0 i = n(1 + 1) = n2 ≥ 2 ⇒ dN ≥ 2 cuando n > 1 Teorema 2.6. ∃ r ≤ d16 log5 (n)e tal que or (n) > 4 log2 (n) Demostraci´on. Supongamos que A = {r1 , . . . , rt } son todos los n´ umeros que cum2 plen que ori (n) ≤ 4 log (n). Cada uno de ellos dividir´a a: 26

b4 log2 (n)c

Y

z=

(ni − 1) < n16 log

4

(n)

≤ 216 log

5

(n)

i=1

Pues nori − 1 = qri ∧ ori ≤ 4 log2 (n) ∀ i Adem´as tenemos que ∀ x ∈ A, x < 16 log5 (n) pues Y

x ≤ z < 216 log

x∈A

5

(n)

⇒

X

x < 16 log5 (n) ⇒ x < 16 log5 (n) ∀ x ∈ A

x∈A

Por otro lado, sea B = {1, . . . , d16 log5 (n)e} Por el lema 2.5 se tiene que: lcm{x ∈ 5 B} > 2d16 log (n)e Adem´as A ⊂ B, pero ¿se puede dar la igualdad? No, pues de darse tend´ıamos que: 2d16 log

5

(n)e

> z > lcm{x ∈ A} = lcm{x ∈ B} > 2d16 log

5

(n)e

]

Por lo que tenemos que A 6= B y por lo tanto ∃ r < d16 log5 (n)e tal que or (n) > 4 log2 (n) Veamos ahora la definici´on de una propiedad importante: Definici´ on 2.7 (N´ umeros introspectivos). Sea un polinomio f (x) y un n´ umero m ∈ m N. Decimos que m es introspectivo para f (x) si y solo si [f (x)] = f (xm ) mod (xr − 1, p) Lema 2.8. a) Si m, n son introspectivos para f (x) entonces mn tambi´en lo es. b) Si m es introspectivo para f (x) y g(x) entonces m tambi´en lo es para f (x)g(x). Demostraci´on. a) Como m es introspectivo paraf (x) tenemos que [f (x)]m = f (xm ) mod (xr − 1, p) ⇒ {[f (x)]m }n = [f (xm )]n mod (xr − 1, p) y como n tambi´en es introspectivo tenemos que [f (x)]mn = [f (xmn )] mod (xr − 1, p) b) Trivial pues [f (x)g(x)]m = f (x)m g(x)m = f (xm )g(xm ) mod (xr − 1, p) pues m es introspectivo tanto para f (x) como para g(x).

Vamos ahora a definir los grupos que nos servir´an para encontrar una contradicci´on que nos asegurar´a la correctitud del algoritmo. Definici´ on 2.9. Sea I = {ni pj con i, j ≥ 0}. Definimos G = {x mod r con x ∈ I} < Z∗r con |G| = t 27

Definici´ on 2.10. Sea qr (x) el r-´esimo polinomio ciclot´omico sobre Zp y h(x) un polinomio de grado or (p) divisor de qr (x). Denotamos ahora: P =< x + 1, . . . , x + l > . y definimos G =

P Zp [x] t si n 6= pb . Pero como |G| = t tenemos que existen m1 > m2 ∈ J tales que m1 = m2 mod r. Por lo tanto xm1 = xm2 mod xr − 1. 28

Sea f (x) ∈ P . Entonces [f (x)]m1 = f (xm1 ) = f (xm2 ) = [f (x)]m2 mod (xr − 1, p). Tenemos entonces que f (x) ∈ G es una ra´ız de q(y) = y m1 − y m2 en √F . Luego q(y) 2 t tiene al menos |G| ra´ıces√ distintas pero δ(q(y)) = m1 ≤ (np)sqrtt < n 2 . Con lo cual 2 t obtenemos que |G| < n 2 Ahora estamos en condiciones de demostrar el converso al teorema 2.4. Teorema 2.15. Si el algoritmo devuelve Primo entonces n es primo. Demostraci´on. Suponemos que el algoritmo ha devuelto Primo. De hacerlo en el cuarto paso estar´ıamos obviamente ante un primo, luego nos queda analizar cuando devuelve Primo en el sexto paso. p Por el lema 2.13 tenemos que si |G| = t y l = b2 ϕ(r) log(n)c entonces:

 |G| ≥ ≥ 2b2

√     √  l − 1 + b2 t log(n)c 2b2 t log(n)c − 1 t+l−2 √ √ ≥ ≥ ≥ t−1 b2 t log(n)c b2 t log(n)c

√

√

t log(n)c

n2 ≥ 2

t

√

Ahora bien, por el teorema 2.14 tenemos que |G| < 1/2n2 t si n 6= pb luego ∃ b > 0 tal que n = pb pero si b > 1 el algoritmo hubiera determinado en el segundo paso que n es compuesto, con lo cual b = 1 y n = p

2.2.

An´ alisis de complejidad

Vamos a comprobar ahora la complejidad del algoritmo. Nos basaremos en el siguiente resultado. Teorema 2.16. a) La adici´on, multiplicaci´on y divisi´on de dos enteros de talla 19 e log(n) se puede realizar en O(log(n)) . b) La adici´on, multiplicaci´on y divisi´on de dos polinomios de grado d con coeficientes e log(n)). de talla a lo sumo log(n) se puede realizar en O(d Demostraci´on. Los detalles y algoritmos se pueden encontrar en el libro [1]. Vayamos paso por paso. 19

e (x)) = O(f (x) logO(1) (logO(1) (n)) = O(f (x) logε (n)) A partir de ahora denotaremos O(f

29

1. Si n = ab para alg´ un a ∈ N y b > 1 entonces Output = Compuesto Para realizar este paso realizamos la factorizaci´on del polinomio xb − n para 1 ≤ b ≤ log(n + 1). Si obtenemos un factor de grado 1 tenemos que: xb − n = (x − a)g(x) ⇒ ab − n = 0 y el algoritmo devuelve Compuesto. 2 e La factorizaci´on de dicho polinomio sobre el Zn se puede realizar en O(log (n)) usando el algoritmo de factorizaci´on descrito en [1]. Ahora bien, como ejecutamos dicho algoritmo un m´aximo de log(n) veces tenemos que este paso se puede realizar 3 e en un m´aximo de O(log (n)) pasos.

2. Encuentra el menor r tal que or (n) > 4 log2 (n) Para este paso probamos de forma secuencial nk 6= 1 mod r con 1 ≤ k ≤ 4 log2 (n) hasta encontrar un r que cumpla dicha propiedad. Por el lema 2.6 sabemos que no son necesarias m´as de O(log5 (n)) pruebas y sabiendo que en cada prueba realizamos O(log2 (n)) multiplicaciones obtenemos que en este paso usamos O(log7 (n)). 3. Si 1 < (a, n) < n para alg´ un a ≤ r entonces Output = Compuesto En este paso realizamos r c´alculos del gcd. Sabemos que cada c´alculo conlleva O(log(n)) operaciones (ver [1]) con lo cual tenemos que este paso realizamos O(log6 (n)) operaciones. 4. Si n ≤ r entonces Output = Primo Este paso es una simple comparaci´on que se realiza en O(1). p 5. Desde a = 1 hasta b2 ϕ(r) log(n)c comprueba a) si (x + a)n 6= xn + a (mod xr − 1, n) entonces Output = Compuesto p En este paso debemos realizar b2 ϕ(r) log(n)c test de nulidad. Para cada uno de ellos debemos realizar O(log(n)) multiplicaciones de polinomios de grado r con e log2 (n)) operacoeficientes no mayores que O(log(n)). Por lo tanto realizamos O(r p e ciones. Con lo cual resulta que la complejidad de este paso es O(r ϕ(r) log3 (n)) = 10,5 e 23 log3 (n)) = O(log e O(r (n)). Como la complejidad de este ultimo domina a todas las anteriores tenemos que 10,5 e este algoritmo tiene una complejidad de O(log (n)). 30

2.3.

Algunas mejoras

Vamos a comentar un poco las mejoras que ya anunci´abamos al final del cap´ıtulo 1.4. A la luz del an´alisis de complejidad es claro que el mejor m´etodo para mejorar el orden del algoritmo es mejorar la cota para r. Eso es exactamente lo que realizamos cuando suponemos cierta las conjeturas de Artin, de Sophie-Germain o de Riemann. Al mejorar las cotas sobre r autom´aticamente se mejoran las cotas de los siguientes bucles. Otra forma de rebajar la complejidad ser´ıa mejorar el conjunto de valores en los que comprobamos la igualdad del paso 5. Esa es la idea de las modificaciones de Berrizbeitia, Qi Cheng y Bernstein. Aunque dichas mejoras finalmente desembocaron en un algoritmo probabilista, la idea fue “mezclar” este algoritmo con los algoritmos ya conocidos de curvas algebraicas. Por u ´ltimo destacar la mejora sustancial que se producir´ıa de ser cierta la conjetura 1.26. Modificando ligeramente la b´ usqueda de r conseguir´ıamos reducir la 3 complejidad a O(log (n)). Esto har´ıa a este algoritmo un test de primalidad extremadamente competitivo que podr´ıa sustituir no solo al ECPP sino a los test probabilistas.

31

3.

Implicaciones del resultado

Comentemos ahora las implicaciones que va a tener este resultado a lo largo de los pr´oximos a˜ nos. La principal y mayor implicaci´on va ha ser la de resolver uno de los problemas te´oricos que tra´ıa de cabeza a los matem´aticos desde hace dos mil a˜ nos. El sue˜ no de Gauss de conseguir un algoritmo capaz de distinguir primos de compuestos ha sido realizado. El principal uso que se le est´a dando a los n´ umeros primos actualmente es el de generador de claves criptogr´aficas. Para ellos son necesarios computar n´ umeros primos exageradamente grandes (t´ıpicamente de 256 d´ıgitos o bits). Para esta labor usualmente se ha usado el test de Miller-Rabin con el posible riesgo que conlleva (´ınfima, pero existente). Si la conjetura 1.26 se confirma, o la implementaci´on de la modificaci´on probabilista resulta ser viable deber´ıan actualizarse todos los sistemas criptogr´aficos a fin de aumentar la seguridad y / o eficiencia (pues ambos test asegurar´ıan la primalidad de los resultados favorables). Ahora bien, este algoritmo no va ha provocar una p´erdida de seguridad pues las claves criptogr´aficas actuales, m´as concretamente del RSA, se basan en el problema de factorizar un n´ umero (no en el problema de la primalidad). Esto es, encontrar p1 , . . . , pi n´ umeros primos y n1 . . . , ni tales que n = pn1 1 . . . pni i . Actualmente, factorizar un n´ umero es un problema extremadamente duro de la clase NP y no parece que vaya a aparecer pronto un algoritmo que lo mejore. Los mejores algoritmo en este campo son algoritmos que se aprovechan de la teor´ıa de curvas el´ıpticas y de la criba de n´ umeros siendo todos ellos bastante complejos. En el libro [3] se encuentra ampliamente desarrollado este tema. Realmente deber´ıa de suceder m´as bien todo lo contrario. El AKS permitir´a encontrar primos con m´as d´ıgitos, y que no pertenezcan a ninguna familia conocida, con mayor facilidad. Lo cual dificultar´ıa la b´ usqueda por fuerza bruta o por los m´etodos de criptoan´alisis m´as comunes. Para finalizar este cap´ıtulo habr´ıa que mencionar tambi´en otro de los grandes descubrimientos. El AKS representa el primer test de nulidad determinista, para un tipo concreto de polinomio, en tiempo polinomial. La idea intuitiva del resultado ser´ıa poder determinar si un polinomio es 0 evaluando en MUY pocos puntos (del orden de O(logO(1) (d)) donde d es el grado del polinomio). Hasta ahora s´olo exist´ıan test probabilistas y el famoso teorema de interpolaci´on polin´omica que necesitaba evaluar en d puntos y por lo tanto exponencial.

32

Se espera que el resultado impulse esta rama de las matem´aticas y abra la puerta a otros descubrimientos en el ´area que permitan mejorar la evaluaci´on de polinomios univariados o multivariados.

33

4.

Implementaci´ on del algoritmo AKS

Tras esta extensa demostraci´on del algoritmo vamos ahora a comentar un poco las motivaciones que pueden llevar a realizar una implementaci´on. Principalmente se pueden resumir en tres causas: Comprobar la velocidad del algoritmo. Comprobar la eficacia de los algoritmos probabilistas. Comprobar la conjetura propuesta por los autores del algoritmo. Para cada uno de ellos dedicaremos m´as adelante un apartado, pero ahora vamos a centrarnos en lo que supuso el proceso de implementaci´on.

4.1.

Implementaci´ on en un paquete de c´ alculo simb´ olico

La primera consideraci´on al plantearnos la implementaci´on del algoritmo fue realizarlo en un paquete comercial de c´alculo simb´olico. La raz´on es simplemente disponer de una las herramientas necesarias para realizar el algoritmos, sin necesidad de programar estructuras de datos para los enteros de precisi´on arbitraria20 ni para los polinomios ni de tener que programar las funciones b´asicas para operar con dichas estructuras. Se consideraron los siguientes paquetes: MAPLE [70]. MuPAD [66]. Magma [68]. Todos ellos de pago. Se decidi´o usar MAPLE por disponer de m´as experiencia con ´el y ser un software de amplio reconocimiento. El programaci´on presentaba tres dificultades claras: la factorizaci´on del primer paso, el c´alculo del orden de r del segundo paso y el test de nulidad del pen´ ultimo paso. MAPLE contaba con funciones propias que realizaban dichas tareas y 20

Recordar que los ordenadores utilizan un sistema num´erico finito. Por lo general el entero m´as grande que puede considerar un ordenador es de 23 2 que para nuestros prop´ositos es un n´ umero rid´ıculo.

34

tras comprobar en la documentaci´on los pormenores se realiza la implementaci´on expuesta en el ap´endice A sin mayores dificultades21 . Las dificultades aparecieron inmediatamente al ejecutarlo para n´ umeros relativamente peque˜ nos. Para n = 20000 el algoritmo tardaba del orden de un minuto en determinar si un n´ umero es primo o no, lo cual es inaceptable cuando se compara con el test que posee MAPLE, basado en el test de Miller-Rabin, cuya ejecuci´on es instant´anea. Al no poder acceder al n´ ucleo de MAPLE y no saber a ciencia cierta que estaba sucediendo para obtener tan malos resultados, conjeturamos la posibilidad de que MAPLE estuviera desarrollando todos los coeficientes del polinomio en el quinto paso, antes de hacer la reducci´on. Lo cual dar´ıa como resultado un algoritmo exponencial. Se program´o una versi´on alternativa al algoritmo que posee MAPLE bas´andose en iterated squaring con reducci´on m´odulo xr −1, n de los coeficientes para controlar el crecimiento, pero el algoritmo resultante result´o ser a´ un m´as ineficiente, con lo que concluimos que MAPLE estaba realizando correctamente la operaci´on y achacamos el pobre rendimiento al propio programa. La implementaci´on se puede consultar en el ap´endice A.1.

4.2.

Implementaci´ on con una librer´ıa de C++

Tras este peque˜ no traspi´es se consider´o usar una librer´ıa de C++. Aqu´ı el proceso de selecci´on fue much´ısimo m´as costoso al tener que leer la documentaci´on de cada librer´ıa para comprobar que pose´ıan las estructuras de datos requeridas y las funciones necesarias. Se consideraron las siguientes librer´ıas: PariGP [67]. LiDIA [69]. NTL [71]. Finalmente se escogi´o la librer´ıa NTL de Victor Shoup por ser la que pose´ıa la documentaci´on m´as clara y todas las herramientas necesarias para la implementaci´on del algoritmo. . . excepto una. Debido a la estructura de la implementaci´on de los polinomios, el grado m´aximo que se puede alcanzar es de 264 insuficiente para 21

Aunque cumpliendo el dicho inform´atico que afirma: “El 20 % del tiempo dedicado a la realizaci´ on de un programa se invierte en la programaci´on. . . mientras que el 80 % restante en su debug”.

35

una prueba en condiciones con los test probabil´ısticos en su propio terreno, los primos industriales 22 . La alternativa era realizar la modificaci´on de la estructura por nosotros mismos pero dicha tarea podr´ıa ser perfectamente, en s´ı misma, uno o dos trabajos dirigidos, por lo que se opt´o por continuar adelante teniendo en cuenta dicha limitaci´on. La programaci´on fue algo m´as compleja debido al entorno menos amigable de una librer´ıa en C++ sobre un software comercial. Se usa un programa de desarrollo integrado, Dev-C++ v4.9.9.2 [59] para ser exactos, que trae como compilador MinGW [60], un “port” para windows del compilador est´andar GCC 3.4.2. De las tres dificultades nombradas anteriormente, la primera y la tercera se pod´ıan solventar con funciones implementadas en el propio paquete, mientras que para el c´alculo del orden hubo que programarse una funci´on. Tras este peque˜ no inconveniente, de f´acil soluci´on, se termina la programaci´on y comienzan los primeros test. La implementaci´on se puede consultar en el ap´endice B.

4.3. 4.3.1.

Experiencias realizadas Benchmark

Una vez obtenida la implementaci´on del algoritmo, el primer paso fue compilarlo23 y realizar una prueba muy simple: buscar todos los primos entre nueve mil y nueve mil cien devolvi´endonos una tabla con el tiempo empleado y si es primo o no. Usamos dicho programa como benchmark en diferentes plataformas obteniendo los siguientes resultados: En la gr´afica 1 representamos el tiempo que tarda la implementaci´on del algoritmo (sin la modificaci´on de la conjetura) a la hora de calcular los n´ umeros primos en el anterior rango (para los dem´as valores el algoritmo tarda un tiempo pr´acticamente despreciable). A la vista de los resultados se observa como la compilaci´on del algoritmo sin optimizar (l´ınea roja) es mucho m´as lenta que su contrapartida optimizada (en todas las plataformas). La gr´afica concuerda completamente con los resultados te´oricos esperados a priori (v´ease, por ejemplo, [61]) sobre potencia de c´alculo de los distintos procesadores (con la sorpresa del buen rendimiento de los procesadores Pentium M, l´ınea magenta). Dicha gr´afica ha sido generada mediante el 22

Primos con 1024 d´ıgitos o bits. Se realiz´ o una compilaci´ on completamente optimizada para ordenadores Pentium 4 y Athlon XP, esto es, para procesadores con las instrucciones SSE2, as´ı como otra sin estas optimizaciones. 23

36

Figura 1: Tiempo de c´alculo de cada procesador.

software MatLab [72] usando los datos generados por la implementaci´on aportados por diversos colaboradores. El script se puede encontrar en el ap´endice C. Hubiera deseado incluir otras arquitecturas, como una estaci´on de trabajo SUN, Macintosh o incluso Linux, pero la imposibilidad de disponer de dichos medios materiales y disponer de compiladores espec´ıficos, no me ha permitido completar la comparativa. 4.3.2.

Computaci´ on GRID

Tras este primer experimento con el programa decidimos realizar un test de c´omputo intensivo. Los objetivos eran los siguientes: Comparar la velocidad del algoritmo AKS con el de Miller-Rabin. Intentar hallar la curva asint´otica de velocidad del algoritmo AKS. Buscar errores en el algoritmo de Miller-Rabin. Estimar la funci´on Π(x), esto es, comprobar emp´ıricamente el teorema de densidad de los n´ umeros primos [10].

37

Para realizar dicha experiencia, temiendo una necesidad de c´alculo excesivo, se buscan alternativas a la ejecuci´on en una buena m´aquina durante periodos extremadamente largos de tiempo. Usando las idea de paralelizaci´on de algoritmos o t´ecnicas de c´omputo GRID (para mayor informaci´on consultar el mayor experimento de c´alculo GRID actualmente en ejecuci´on, el proyecto SETI@home [62] o el proyecto europeo DataGrid [64] del cual el IFCA es un miembro participante) recurrimos a separar el c´alculo en los ocho ordenadores del aula de inform´atica que posee el departamento de Matem´aticas, Estad´ıstica y Computaci´on. Las particularidades de este algoritmo posibilitan un paralelismo muy acusado. Se ve claramente que el cuello de botella se forma en el bucle del pen´ ultimo paso. Ahora bien, como cada iteraci´on del bucle es completamente independiente y no es necesario, aunque si aconsejable, realizarlas en un orden determinado, se podr´ıa paralelizar el algoritmo ejecutando una iteraci´on en cada microprocesador disponible. Esto posibilitar´ıa una reducci´on en un factor k la complejidad del algoritmo, donde k es el n´ umero de procesadores disponible. Como no se dispon´ıa de ning´ un entorno multiprocesador donde ejecutar el algoritmo y desconozco los detalles de la implementaci´on que con lleva dicha modificaci´on, finalmente no se realiz´o la experiencia24 . Otra idea de paralelizaci´on consist´ıa en repartir los n´ umeros, sobre los que se iba a realizar el test, entre los distintos ordenadores. De esta forma cada ordenador corr´ıa el programa original sobre un conjunto de n´ umeros de forma independiente. Lo ideal hubiera sido seguir un modelo Cliente-Servidor (ver figura 2) que es el usado en los programas de c´omputo GRID como los mencionados anteriormente. El modelo es algo as´ı como tener un ordenador corriendo un software especial (servidor) que se encargar´ıa de repartir el trabajo de forma din´amica sobre los dem´as ordenadores, que correr´ıan las aplicaciones clientes. Esto es, un ordenador cliente, contacta con el servidor y pide trabajo, que en este caso ser´ıa un rango de n´ umeros. El servidor se lo env´ıa y lo marca como en proceso. El servidor debe asegurar que nunca se env´ıa el mismo rango a dos ordenadores a la vez y que nunca se computa dos veces el mismo rango de n´ umeros. Tambi´en debe encargarse de enviar rangos de n´ umeros de forma que la media de tiempo que se tarde sea la misma para cada rango. Esto se consigue suponiendo que el crecimiento sigue una curva polinomial mon´otona creciente, con lo cual el tama˜ no de los rangos decrece al aumentar el n´ umero de cifras. Si pasado un tiempo no ha recibido la respuesta desmarca ese rango y lo vuelve a asignar a 24

La implementaci´ on se realiza a nivel de lenguaje de programaci´on usando t´ecnicas de multithread [58], literalmente, multihilos.

38

otro ordenador. En caso de que obtenga respuesta marca el rango como procesado y se encarga de ensamblar los resultados en el archivo de salida.

Figura 2: Diagrama de programaci´on cliente-servidor.

Esta idea se descart´o, parcialmente, al conllevar una programaci´on mucho m´as delicada y de alto nivel, la cual no es el objetivo de este trabajo. Sin embargo se realiz´o una paralelizaci´on est´atica adoptando yo el papel de servidor, repartiendo los rangos a mano y, en principio, ensambl´andolos tambi´en. El resultado fue un fracaso absoluto. El tiempo previsto de c´alculo no era ni una d´ecima parte del necesitado en realidad, aparte del inconveniente de ser un aula en uso, con lo cual el programa fue cerrado antes de completar sus tareas en pr´acticamente todos los ordenadores. 4.3.3.

Prueba de estr´ es al algoritmo de Miller-Rabin

Despu´es de este traspi´es la siguiente prueba fue buscar, por fuerza bruta, un error en el algoritmo de Miller-Rabin. Haciendo k = 1 (recordar que k era el par´ametro que contaba el n´ umero de iteraciones del algoritmo y era el factor relevante para la estimaci´on de la probabilidad de error) y ejecutando un mill´on de veces sobre un n´ umero de Carmichael que escogimos de entre la lista obtenida de [33]. El fichero de salida ocupa del orden de 11 MB de informaci´on y de forma asombrosa muestra que el algoritmo NO fall´o en ninguna ocasi´on, en contra de la probabilidad estimada a priori. Dichos datos nos hace sospechar, aunque en la documentaci´on de la librer´ıa no lo deja muy claro, que el algoritmo implementado NO es el Miller-Rabin cl´asico, sino una combinaci´on de ´este con otros test como, por ejemplo, con el test de pseudoprimos de Lucas [40], combinaci´on usada, por ejemplo en el paquete de c´alculo 39

simb´olico Mathematica [39]. Por falta de tiempo no se ha procedido a un estudio sistem´atico del c´odigo fuente de librer´ıa para averiguar dicho dato. Otra posibilidad ser´ıa que el n´ umero escogido no fuera realmente un n´ umero de Carmichael, aunque dicha posibilidad es mucho menos plausible a priori. La modificaci´on propuesta para la realizaci´on de este experimento se puede encontrar en el ap´endice B.1. 4.3.4.

Verificaci´ on de la conjetura 1.26

Por u ´ltimo, se realiz´o un test similar al segundo propuesto, pero esta vez ejecutado con la modificaci´on que hace al algoritmo de orden O(log3 (n)). Para ello realizamos en paralelo una llamada a nuestro algoritmo modificado y al algoritmo de Miller-Rabin. Cuando los resultados difieran llamamos al algoritmo est´andar AKS. Los resultados emp´ıricos muestran que la conjetura NO es v´alida, pues falla sobre algunos n´ umeros. La prueba se ha realizado en dos tandas, la primera vez sobre los primeros diez mil n´ umeros primos y en la segunda sobre los veinte mil primeros. Ambas lista han sido sacadas de [18]. Se observa, adem´as, que el algoritmo es s´olo un poco m´as lento que Miller-Rabin, aun siendo una implementaci´on susceptible de mejoras (la implementaci´on del paso 1 se puede mejorar notablemente y otras partes del c´odigo son probablemente tambi´en mejorables). Sorprendentemente, esta vez s´ı han aparecido n´ umeros en los que el algoritmo de Miller-Rabin falla, lo cual nos ha llevado a repetir en dichos n´ umeros, el test anterior. Para nuestra sorpresa ahora efectivamente produce salidas con errores de forma aleatoria, pero NO en los n´ umeros de Carmichael. Los resultados de dos ejecuciones de dicha prueba se pueden encontrar en el ap´endice E. Se observa un fen´omeno curioso, por muchas veces que se ejecute el test, siempre se obtiene el mismo n´ umero de errores y en los mismos n´ umeros. La pregunta es ¿c´omo es posible, siendo el algoritmo aleatorio? La respuesta es bien simple, desconocemos como se ha implementado la aleatoriedad en el m´etodo. Lo m´as probable es que NO se cambie la semilla de aleatoriedad, por defecto, en cada ejecuci´on y por lo tanto, bajo la misma compilaci´on del ejecutable, se obtengan exactamente los mismo resultados. Para comprobar esto habr´ıa que estudiar en profundidad, de nuevo, la implementaci´on del test en la librer´ıa.

40

4.3.5.

Prueba de estr´ es al algoritmo de Miller-Rabin, otra vez

A ra´ız de los resultados del anterior experimento realizamos la modificaci´on propuesta en el ap´endice B.3. Pretendemos evaluar que impacto tiene el n´ umero de iteraciones del algoritmo de Miller-Rabin en la cantidad de errores obtenidos. De esta experiencia obtenemos como resultado una tabla con los fallos de realizar cien mil test sobre uno de los n´ umeros problem´aticos. Presentamos los datos en la siguiente gr´afica, obtenida a partir de los datos mostrados en el ap´endice E. Se observa como la probabilidad de error cae de forma brutal al aumentar el n´ umero de iteraciones. Con cinco iteraciones se puede considerar la probabilidad de error como 0. Es importante tener en cuenta que un aumento en el n´ umero de iteraciones no tiene un impacto muy grande en el tiempo de c´alculo (en nuestro caso es 0) y que “por defecto”se realizan diez iteraciones, un n´ umero m´as que suficiente para asegurar la primalidad a la vista de nuestros datos.

Figura 3: Estimaci´on de la probabilidad de error.

4.4.

Conclusiones derivadas de la implementaci´ on

A la vista de los resultados se observa que el algoritmo est´andar no puede competir con los algoritmo probabilistas tipo Miller-Rabin, ni en tiempo, ni en efectividad. 41

Esto viene a reafirmar los argumentos que defienden la computaci´on probabilista, pues es un claro ejemplo de efectividad de dichos m´etodos. Sin embargo, el algoritmo modificado se comporta de manera extraordinaria y es capaz de enfrentarse en igualdad de condiciones a los algoritmos probabilistas. Es necesario un mayor estudio de los posibles errores que se puede cometer al utilizar dicho algoritmo, o dar una demostraci´on de la conjetura a fin de comprobar la efectividad del algoritmo.

42

A.

Implementaci´ on del algoritmo en MAPLE

Presentamos aqu´ı una peque˜ na implementaci´on del algoritmo en el software comercial MAPLE. AKS:=proc ( n : : posint ) #Rutina que comprueba s i un numero e s primo o e s compuesto mediante #e l a l g o r i t m o c o n o c i d o por AKS. Acepta como i n p u t un numero e n t e r o #p o s i t i v o y d e v u e l v e 0 s i e s compuesto o 1 s i e s primo . #V a r i a b l e s l o c a l e s l o c a l i : : posint , aux : : l i s t , r : : posint ; #i #aux #j #r #orden

contadores l i s t a donde poner l a f a c t o r i z a c i o n polinomio ( expresion ) modulo s o b r e e l que d i v i d i m o s guardo e l orden

with ( numtheory , order ) ; #Paso 1 i :=2: while ( c e i l ( log ( n))> i ) do aux := f a c t o r s ( xˆ i −n ) mod n : #f a c t o r i z o . f o r j in aux [ 2 ] do i f degree ( j [ 1 ] ) = 1 then RETURN ( 0 ) ; f i : end do : #compruebo s i n = ai , s i hay f a c t o r e s de grado 1 . i := i +1: end do : #s i s a l e de a q u i 6 ∃ a, i t a l e s que ai = n . #Paso 2 r :=2: orden :=order ( n , r ) ; #C a l c u l o e l orden i f evalb ( orden=FAIL) then orden : = 0 ; f i ; #compruebo s i hay d i v i s o r e s de 0 while ( orden < round ( 4 ∗ ( log ( n ) ) ˆ 2 + 1 ) ) do r := r +1; orden :=order ( n , r ) ; i f evalb ( orden=FAIL) then orden : = 0 ; f i ; end do ; #o b t e n g o r t a l que or (n) > 4log 2 (n) #Paso 3 f o r i from 2 to r do i f evalb ( gcd ( i , n)1) and i i ) do aux := f a c t o r s ( xˆ i −n ) mod n : #f a c t o r i z o . f o r j in aux [ 2 ] do i f degree ( j [ 1 ] ) = 1 then RETURN ( 0 ) ; f i : end do : #compruebo s i n = ai , s i hay f a c t o r e s de grado 1 . i := i +1: end do : #s i s a l e de a q u i 6 ∃a, i t a l e s que ai = n . #Paso 2 r :=2: orden :=order ( n , r ) ; #c a l c u l o e l orden i f orden=FAIL then orden : = 0 ; f i ; #compruebo s i hay d i v i s o r e s de 0 while ( orden < round ( 4 ∗ ( log ( n ) ) ˆ 2 + 1 ) ) do r := r +1; orden :=order ( n , r ) ; i f orden=FAIL then orden : = 0 ; f i ; end do ; #o b t e n g o r t a l que or (n) > 4log 2 (n) #Paso 3 f o r i from 2 to r do i f gcd ( i , n)1 and i a >> b >> o p c i o n ; // l e o l i m i t e s e n t r a d a . c l o s e ( ) ; // c i e r r o f i c h e r o o f s t r e a m s a l i d a ; // o b j e t o de l a c l a s e o f s t r e a m s a l i d a . open ( ” s a l i d a . t x t ” , i o s : : out ) ; // ab ro a r c h i v o c l o c k t t o t a l ; // tiempo t o t a l c l o c k t t ; // v a r i a b l e que c o n t r o l a e l tiempo s a l i d a