Primalidad

PRIMALIDAD Paula Muñoz Ramírez PRIMALIDAD Paula Muñoz Ramírez Memoria presentada como parte de los requisitos para la obtención del título de Grado en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Tutor José María Tornero Sánchez Índice general Abstract 1 Resumen 3 1. El problema de la Primalidad. 5 1.1. Áreas de influencia. ............................ 6 1.2. Algunos algoritmos de primalidad. .................... 9 2. Notación y preliminares matemáticos 13 2.1. Notación .................................. 13 2.2. Preliminares ................................ 13 2.3. Resultados de interés ........................... 14 3. El algoritmo AKS y su corrección 19 3.1. Antes de empezar ............................. 19 3.2. El algoritmo (I) ............................... 21 3.3. Interludio introspectivo .......................... 24 3.4. El algoritmo (II) .............................. 25 ii primalidad 4. Análisis de la complejidad 29 5. Un ejemplo concreto 33 Abstract The aim of this work is to present a deterministic method that establishes with absolute certainty whether a given number is a prime or not. In order to give an answer to this question, we will study in depth the AKS algorithm, which gives a theoretical polynomial–time solution to the Primality problem. The first chapter is devoted to give an introduction of what being a prime means, as well as presenting the Primality problem. We will talk about some subjects, from both Mathematics and Computer Science, where this problem plays an essential role. Moreover, we will make a distinction between probabilistic primality tests and deterministic primality tests, giving an example for each case. In the second chapter, we will introduce some notations that we will use through the text. In addition to this, we will also show and recall several previous concepts that will help us in the sequel. During the third chapter we will be presenting the AKS algorithm as well as developing the ideas and mathematical concepts behind this test that verifies its correctness. We will use not only modular arithmetic but also group theory in order to build some results that allow us to prove the primality of a certain number in a satisfactory way. Throughout the fourth chapter we will be studying the complexity of AKS algorithm using basic notions of complexity theory. Eventually, in the last chapter we will give an example of the AKS algorithm, providing us a detailed study of each step. Resumen El objetivo de este trabajo es exponer un método determinístico para, dado un cierto entero 𝑛, poder afirmar con total certeza si es o no primo. Para ello estudiaremos en profundidad el algoritmo determinístico AKS [PinP] que da una solución computacionalmente eficaz (esto es, en tiempo logarítmico) al problema de la Primalidad. Dedicaremos el primer capítulo a introducir el concepto de número primo, así como el problema de la Primalidad. Veremos algunas áreas, tanto de las matemáticas como de las ciencias de la computación, en las que tanto dicho problema como los números primos en sí mismos juegan un papel fundamental. Por otra parte haremos una distinción entre tests de primalidad probabilísticos y tests de primalidad determinísticos, tomando algunos algoritmos como ejemplo en cada caso. En el segundo capítulo introduciremos algunas notaciones que adoptaremos a lo largo del texto, además de exponer o recordar diversos conceptos previos para el desarrollo de nuestro tema. A lo largo del tercer capítulo, expondremos el algoritmo AKS y desarrollaremos las ideas y conceptos matemáticos que se encuentran detrás de él y que verifican su corrección. Haremos uso de la aritmética modular y de la teoría de grupos para construir una serie de resultados que permitan demostrar la primalidad de un cierto número de manera satisfactoria. Siguiendo con el algoritmo AKS, en el cuarto capítulo se estudia la complejidad del mismo, haciendo uso de resultados básicos de la teoría de la complejidad. Finalmente, en el último capítulo emplearemos el algoritmo AKS para determinar la primalidad de un cierto valor 𝑛, haciendo un estudio detallado de cada paso. 10 primalidad 𝑛=𝑝𝛼1 1 ⋅... ⋅𝑝𝛼𝑠 𝑠, denominamos símbolo de Jacobi (de 𝑎sobre 𝑛) a (𝑎 𝑛)=(𝑎 𝑝1)𝛼1 ⋯(𝑎 𝑝𝑠)𝛼𝑠 . Una vez conocemos esta definición, podemos enunciar un resultado basado en una modificación del Teorema de Fermat empleando el símbolo de Jacobi. Lema 1.1.Dados 𝑎∈ℤy𝑝un número primo, se verifica: (𝑎 𝑝)=𝑎𝑝−1 2m od 𝑝. Basándonos en la definición anterior y este último resultado consideramos la siguiente definición. Definición 1.2. Dados 𝑎∈ℤy𝑛un número compuesto e impar, diremos que 𝑛es un pseudoprimo de Euler en base 𝑎si ambos verifican las dos condiciones siguientes: gcd(𝑎, 𝑛)=1,(𝑎 𝑛)=𝑎𝑛−1 2m od 𝑛. Una vez conocemos los anteriores resultados es bastante sencillo de comprender el test de primalidad de Solovay-Strassen [TCYC]. Sea 𝑛un número el cuál queremos ver si es o no primo. En primer lugar debemos tomar aleatoriamente un cierto número 𝑎tal que 𝑎∈ {2,3, ..., 𝑛 − 1} y nos aseguramos de que gcd(𝑎, 𝑛)=1. Una vez conocido dicho valor, comprobamos si se verifica (𝑎 𝑛)=𝑎𝑛−1 2m od 𝑛. Si 𝑛no es un pseudoprimo de Euler en base 𝑎podemos afirmar que 𝑛es un número compuesto, en caso afirmativo, repetiríamos el proceso y lo haremos un cierto número fijo, 𝑚, de veces. Si, tras reiterar el desarrollo 𝑚veces, para ningún 𝑎cumpliendo lo anterior se ha verificado que 𝑛no es un pseudoprimo de Euler en base 𝑎, ciertos resultados sobre la distribución de estos pseudoprimos nos permiten asegurar con una probabilidad de 1 − (1∕2)𝑚que 𝑛es primo. De esta forma, variando 𝑚podemos conseguir una elevada probabilidad de que nuestro candidato 𝑛sea primo (o bien la certeza de que no lo es). 1. el problema de la primalidad. 11 La otra gran familia de test de primalidad es la de los algoritmos determinísticos. Estos son aquellos que aportan una respuesta precisa a la pregunta de si es 𝑛primo. Dichos protocolos presentan la solución, al contrario que los test probabilísticos, sin ningún margen de error. Entre ellos podemos encontrar la criba de Eratóstenes o el test de AKS. La criba de Eratóstenes fue diseñada por el matemático griego Eratóstenes, que le da su nombre, y tiene como función encontrar todos los números primos menores que un cierto 𝑛dado. Veamos como funciona. En primer lugar debemos escribir en una lista los números naturales comprendidos entre el 2 y 𝑛, incluyendo a estos. Comenzaremos escogiendo el primer número no marcado de la lista, que es el número 2 y marcaremos todos los múltiplos de 2, exceptuando el mismo, pues es primo. A continuación seleccionaremos el siguiente elemento no marcado de nuestro registro, 𝑞, que será el siguiente número primo y volveremos a marcar aquellos que sean múltiplos de este, exceptuando el propio número 𝑞. Dicho procedimiento se reiterará hasta haber seleccionado en alguna ocasión todos aquellos elementos no marcados de la lista. Una vez finalizado esto, los números que quedan sin marcar en nuestro registro tras haber aplicado la criba son todos los números primos menores que el cierto número 𝑛dado. Este algoritmo se basa en el hecho de que todo número compuesto debe ser dividido por algún número primo, luego por ello vamos eliminando aquellos naturales que son divididos por los primos que vamos seleccionando. Es más, aunque no parezca claro en el desarrollo del algoritmo nos bastará con reiterar los pasos hasta llegar a √𝑛, pues de ser 𝑛compuesto, deberá tener al menos un factor primo menor que √𝑛. Por otra parte, otro algoritmo determinístico interesante es el test AKS, el cual es relativamente nuevo, fue desarrollado a principios del siglo XXI por Manindra Agrawal, profesor del Departamento de Ciencias de la Computación del Indian Institute of Technology, junto con Neeraj Kayal y Nitin Saxena, estudiantes en la misma institución, como se comenta en [BFE]. Dicho algoritmo fue presentado por primera vez en [PinP] y su importancia reside en su capacidad de concluir, en tiempo logarítmico, si un cierto número es o no primo con total seguridad, de manera determinística, a diferencia de los tests probabilísticos mencionados anteriormente, que no nos dan el resultado con total seguridad. Esto supuso un gran avance dentro del campo de las ciencias de la computación, pues la discusión de que el problema de la Primalidad se encontrase en la clase Pde complejidad era un problema abierto, hasta que Agrawal, 12 primalidad Kayal y Saxena desarrollaron su algoritmo, conocido actualemente como AKS. Dicho algoritmo demostró que es posible probar si un número es primo o no en un tiempo polinomial. Sin embargo, en la práctica no es muy útil para números considerablemente grandes, luego su interés es meramente teórico por ahora y, por ende, en la práctica sigue haciéndose uso de los algoritmos probabilísticos que son mucho más rápidas. A lo largo de este trabajo estudiaremos las ideas y técnicas matemáticas que se encuentran tras este algoritmo y que lo hacen tan interesante. Nos basaremos en [PinP] para ello. 2 Notación y preliminares matemáticos 2.1 Notación Usaremos 𝑞𝑘∥𝑛para notar que 𝑞𝑘∣𝑛pero 𝑞𝑘+1 ∤𝑛. Para el estudio de la complejidad emplearemos la notación de la soft-, esto es 𝑓(𝑛) =  (𝑔(𝑛)) que equivale a 𝑓(𝑛) = (𝑔(𝑛) log𝑘(𝑔(𝑛)))(para un cierto 𝑘). También usaremos la big omega, siendo 𝑓(𝑛) = Ω(𝑔(𝑛)) equivalente a 𝑔(𝑛) = (𝑓(𝑛)). Esto es, 𝑓está acotada inferiormente por 𝑔de forma asintótica, ∃𝑘 > 0,∃𝑛0|∀𝑛>𝑛0se tiene que 𝑓(𝑛)≥𝑘⋅𝑔(𝑛). Por último, usaremos en lo sucesivo log(⋅)para denotar el logaritmo en base 2, como es habitual en teoría de la complejidad. 2.2 Preliminares En esta sección recordaremos diversas definiciones y teoremas que hemos visto a lo largo de la carrera y que nos serán de gran utilidad a la hora de desarrollar el algoritmo AKS. Definición 2.1. Sean 𝑟∈ℕ,𝑎∈ℤtal que gcd(𝑎, 𝑟)=1. El orden de 𝑎módulo 𝑟es el menor 𝑘tal que 𝑎𝑘≡1(mod 𝑟). Lo denotaremos por 𝑜𝑟(𝑎). Definición 2.2. Sea 𝑟∈ℤ≥0. La función phi de Euler, que notaremos por 𝜙(𝑟), da el número de enteros positivos menores o iguales que 𝑟que son primos relativos con 𝑟. 14 primalidad Observación 2.1.Sea 𝑟∈ℕ, para todo 𝑎∈ℤtal que gcd(𝑎, 𝑟)=1, se cumple que 𝑜𝑟(𝑎) ∣ 𝜙(𝑟). Esto es consecuencia directa del Teorema de Lagrange. Teorema 2.1 (Pequeño teorema de Fermat). Sea 𝑎∈ℤtal que 𝑎 > 0y𝑝primo. Entonces 𝑎𝑝≡𝑎(mod 𝑝). En particular, si 𝑝∤𝑎,𝑎𝑝−1 ≡1(mod 𝑝). Definición 2.3. Dado un cuerpo 𝐾definimos como el polinomio ciclotómico de orden 𝑛sobre 𝐾, denotado Φ𝑛(𝑋), como el polinomio mónico de 𝐾[𝑋]que tiene por raíces todas las raíces primitivas de la unidad de orden 𝑛en 𝐾. Para el cálculo de Φ𝑛(𝑋)consideraremos el polinomio 𝑋𝑛− 1, cuyas raíces son todas las raíces 𝑛-ésimas de la unidad. Cada una de estas raíces, a su vez, es una raíz 𝑗-ésima primitiva de la unidad para un cierto 𝑗, divisor de 𝑛. Del mismo modo, si consideramos Φ𝑗con 𝑗∣𝑛, todas sus raíces también son raíces de 𝑋𝑛− 1. Luego de esto deducimos que 𝑋𝑛− 1 = ∏ 𝑗∣𝑛 Φ𝑗(𝑋). Despejando de la igualdad anterior, obtenemos un procedimiento recursivo para la obtención de polinomios ciclotómicos: Φ𝑛(𝑋) = 𝑋𝑛− 1 ∏ 𝑗∣𝑛,𝑗≠𝑛 Φ𝑗(𝑋) . Teorema 2.2. Dado un cuerpo 𝐾, consideremos el cuerpo ciclotómico 𝐾(𝑛), que es la extensión algebraica simple del cuerpo 𝐾obtenida al adjuntarle las raíces 𝑛-ésimas de la unidad. Si 𝐾=𝔽𝑞, con gcd(𝑛, 𝑞)=1, entonces Φ𝑛factoriza en 𝜙(𝑛)∕𝑜𝑛(𝑞)distintos polinomios mónicos irreducibles en 𝐾[𝑋], todos ellos de grado 𝑜𝑛(𝑞). Podemos encontrar una prueba de este teorema en [FFA]. 2.3 Resultados de interés A continuación enunciaremos y demostraremos una serie de lemas previos que emplearemos a lo largo del siguiente capítulo en el desarrollo matemático del algoritmo. 2. notación y preliminares matemáticos 15 En primer lugar, denotaremos por 𝑑𝑛al mínimo común múltiplo de los primeros 𝑛números enteros positivos, que nos será útil en el siguiente lema. Lema 2.1.Para 𝑛≥7,𝑑𝑛≥2𝑛. Demostración. Para 1≤𝑚≤𝑛, consideremos la integral: 𝐼(𝑚, 𝑛) = ∫1 0 𝑥𝑚−1(1 − 𝑥)𝑛−𝑚𝑑𝑥 = 𝑛−𝑚 ∑ 𝑟=0 (−1)𝑟⋅(𝑛−𝑚 𝑟)⋅ 1 𝑚+𝑟, que se tiene directamente del binomio de Newton (la prueba se puede encontrar en [CIP]). Haciendo integración por partes de forma reiterada tenemos: 𝐼(𝑚, 𝑛) = ∫1 0 𝑥𝑚−1  (1 − 𝑥)𝑛−𝑚𝑑𝑥 = 0 + 𝑚− 1 𝑛−𝑚+ 1 ⋅∫1 0 𝑥𝑚−2 ⋅(1 − 𝑥)𝑛−𝑚+1𝑑𝑥 = 0 + (𝑚− 1) ⋅(𝑚− 2) (𝑛−𝑚+ 1) ⋅(𝑛−𝑚+ 2) ⋅∫1 0 𝑥𝑚−3 ⋅(1 − 𝑥)𝑛−𝑚+2𝑑𝑥 =…= =(𝑚− 1) ⋅(𝑚− 2) ⋅…⋅1 (𝑛−𝑚+ 1) ⋅(𝑛−𝑚+ 2) ⋅…⋅𝑛=𝑚⋅(𝑚− 1) ⋅(𝑚− 2) ⋅…⋅1 𝑚⋅(𝑛−𝑚+ 1) ⋅(𝑛−𝑚+ 2) ⋅…⋅𝑛 =1 𝑚⋅(𝑛 𝑚) Claramente 𝐼(𝑚, 𝑛)⋅𝑑𝑛∈ℤpues, fijándonos en la parte derecha de la expresión de 𝐼(𝑚, 𝑛), vemos que (𝑛−𝑚 𝑟)⋅(−1)𝑟es entero para cualquier 𝑟y, además, 𝑚+𝑟(donde 𝑟∈ {0,…, 𝑛 −𝑚}) se puede simplificar en cada sumando con algún factor de 𝑑𝑛. Luego podemos concluir que 𝐼(𝑚, 𝑛)⋅𝑑𝑛∈ℤ. De esta forma, como 𝐼(𝑚, 𝑛)⋅𝑑𝑛∈ℤ, tenemos que 𝑚⋅(𝑛 𝑚)∣𝑑𝑛para cualquier 𝑚, con 1≤𝑚≤𝑛. Como consecuencia de ello, tomando unos valores específicos para 𝑚 y𝑛, vamos a poder acotar inferiormente 𝑑𝑛. En particular, si tomamos 𝑛= 2𝑛y𝑚=𝑛, tenemos que 𝑛⋅(2𝑛 𝑛)∣𝑑2𝑛, y, como por definición, 𝑑2𝑛∣𝑑2𝑛+1, se observa que: 𝑛⋅(2𝑛 𝑛)∣𝑑2𝑛+1.(I) Por otra parte, haciendo 𝑛= 2𝑛+ 1 y𝑚=𝑛+ 1 en 𝑚⋅(𝑛 𝑚)∣𝑑𝑛obtenemos (𝑛+ 1) ⋅(2𝑛+ 1 𝑛+ 1 )∣𝑑2𝑛+1. 16 primalidad Vamos a analizar un poco más el término de la derecha. Si desarrollamos el número combinatorio (2𝑛 𝑛)y multiplicamos por 2𝑛+ 1 nos queda la siguiente igualdad: (2𝑛+ 1) ⋅(2𝑛 𝑛)=(2𝑛+ 1) ⋅2𝑛⋅(2𝑛− 1) ⋅…⋅(2𝑛−𝑛+ 1) 𝑛⋅(𝑛− 1) ⋅…⋅1 =(𝑛+ 1) ⋅(2𝑛+ 1) ⋅2𝑛⋅…⋅(𝑛+ 1) (𝑛+ 1) ⋅…⋅1= (𝑛+ 1) ⋅(2𝑛+ 1 𝑛+ 1 ). Así pues (2𝑛+ 1) ⋅(2𝑛 𝑛)∣𝑑2𝑛+1.(II) Como gcd(𝑛, 2𝑛+ 1) = 1, podemos deducir de (I) y (II) que 𝑛⋅(2𝑛+ 1) ⋅(2𝑛 𝑛)∣𝑑2𝑛+1. Entonces 𝑑2𝑛+1 ≥𝑛⋅(2𝑛+ 1) ⋅(2𝑛 𝑛)≥𝑛⋅4𝑛, donde la última desigualdad se sigue del hecho de que (2𝑛 𝑛)es el mayor de los 2𝑛+ 1 términos de la expresión de (1 + 1)2𝑛. Si 𝑛≥2, entonces 𝑑2𝑛+1 ≥22⋅𝑛+1 = 4𝑛⋅2. Por otra parte, si 𝑛≥4, entonces 𝑑2𝑛+2 ≥𝑑2𝑛+1 ≥22𝑛+2. Por tanto 𝑑𝑛≥2𝑛, como queríamos demostrar. Probemos ahora la siguiente desigualdad. Lema 2.2.Para 𝑛∈ℕse cumple que 𝑛⌈log2(𝑛)⌉ ∏ 𝑖=1 (𝑛𝑖− 1) < 𝑛log4(𝑛). Demostración. Supondremos que 𝑛 > 3, ya que los casos restantes se comprueban inmediatamente. Por un lado tenemos 𝑛⌈log2(𝑛)⌉ ∏ 𝑖=1 (𝑛𝑖− 1) < 𝑛 ⌈log2(𝑛)⌉ ∏ 𝑖=1 (𝑛⌈log2(𝑛)⌉− 1)=𝑛⋅(𝑛⌈log2(𝑛)⌉− 1)⌈log2(𝑛)⌉ 2. notación y preliminares matemáticos 17 Desarrollemos ahora empleando el binomio de Newton 𝑛⋅(𝑛⌈log2(𝑛)⌉− 1)⌈log2(𝑛)⌉=𝑛⋅⌈log2(𝑛)⌉ ∑ 𝑖=0 (⌈log2(𝑛)⌉ 𝑖)⋅𝑛⌈log2(𝑛)⌉−𝑖⋅(−1)𝑖 < 𝑛 ⋅⌈log2(𝑛)⌉ ∑ 𝑖=0 (⌈log2(𝑛)⌉ 𝑖)⋅𝑛⌈log2(𝑛)⌉−𝑖 < 𝑛 ⋅⌈log2(𝑛)⌉ ∑ 𝑖=0 (⌈log2(𝑛)⌉ 𝑖)⋅𝑛⌈log2(𝑛)⌉ =𝑛⌈log2(𝑛)⌉+1 ⋅⌈log2(𝑛)⌉ ∑ 𝑖=0 (⌈log2(𝑛)⌉ 𝑖) Ahora bien, como ya sabemos, ∑𝑥 𝑖=0 (𝑥 𝑖)= (1 + 1)𝑥= 2𝑥, luego haciendo 𝑥= ⌈log2(𝑛)⌉tenemos 𝑛⌈log2(𝑛)⌉+1 ⋅⌈log2(𝑛)⌉ ∑ 𝑖=0 (⌈log2(𝑛)⌉ 𝑖)≤𝑛log2(𝑛)+2 ⋅2⌈log2(𝑛)⌉ ≤𝑛log2(𝑛)+2 ⋅2log2(𝑛)+1 =𝑛log2(𝑛)+2 ⋅2⋅(2log(𝑛))log(𝑛) =𝑛log2(𝑛)+2 ⋅2⋅𝑛log(𝑛) = 2 ⋅𝑛log2(𝑛)+log(𝑛)+2 Como 𝑛 > 3ylog(𝑛)≥2, tenemos 2⋅𝑛log2(𝑛)+log(𝑛)+2 ≤𝑛log2(𝑛)+log(𝑛)+2+1 ≤𝑛log2(𝑛)+log(𝑛)+log(𝑛)+1 =𝑛log2(𝑛)+2 log(𝑛)+1 =𝑛(log(𝑛)+1)2 ≤𝑛(log(𝑛)+log(𝑛))2=𝑛log4(𝑛). Luego se tiene la desigualdad como queríamos probar. Finalmente, estudiemos el siguiente resultado combinatorio. Lema 2.3.Para 𝑛∈ℤse cumple que (2𝑛+ 1 𝑛)>2𝑛+1.(2.1) 18 primalidad Demostración. Realizaremos esta prueba por inducción. Para 𝑛= 2, tenemos directamente (5 2)=5⋅4⋅3⋅2⋅1 1⋅2= 60 >23= 8. Supongámoslo cierto para 𝑛y probémoslo para 𝑛+ 1 viendo que se cumple (2(𝑛+ 1) + 1 𝑛+ 1 )>2(𝑛+1)+1,o sea, (2𝑛+ 3 𝑛+ 1 )>2𝑛+2. (2(𝑛+ 1) + 1 𝑛+ 1 )=(2𝑛+ 3)! (2𝑛+ 3 − (𝑛+ 1))! ⋅(𝑛+ 1)! =(2𝑛+ 3)! (𝑛+ 1)! ⋅(𝑛+ 2)! = =(2𝑛+ 3) ⋅(2𝑛+ 2) ⋅(2𝑛+ 1)! (𝑛+ 1) ⋅(𝑛+ 2) ⋅𝑛!⋅(𝑛+ 1)! Usando la hipótesis de inducción tenemos: (2𝑛+ 3) ⋅(2𝑛+ 2) ⋅(2𝑛+ 1)! (𝑛+ 1) ⋅(𝑛+ 2) ⋅𝑛!⋅(𝑛+ 1)! >(2𝑛+ 3) ⋅(2𝑛+ 2) (𝑛+ 1) ⋅(𝑛+ 2) ⋅2𝑛+1 =2𝑛+ 3 𝑛+ 2 ⋅2𝑛+2 >2𝑛+2, que es lo que queríamos probar. 3 El algoritmo AKS y su corrección Para estudiar el desarrollo matemático del algoritmo AKS seguiremos el artículo [PinP]. 3.1 Antes de empezar El test de primalidad que expondremos en la siguiente sección se basa en una generalización del pequeño teorema de Fermat, reflejada en el siguiente lema. Lema 3.1.Sea 𝑎∈ℤ,𝑛∈ℕ,𝑛≥2ygcd(𝑎, 𝑛)=1. Entonces 𝑛es primo si y sólo si (𝑋+𝑎)𝑛≡𝑋𝑛+𝑎(mod 𝑛).(3.1) Demostración. Para 0< 𝑖 < 𝑛, los coeficientes de 𝑋𝑖en (𝑋+𝑎)𝑛− (𝑋𝑛+𝑎)son (𝑛 𝑖)⋅𝑎𝑛−𝑖. Distingamos 2 casos: cuando 𝑛es primo y cuando 𝑛es compuesto. Sea 𝑛primo. En este caso tenemos (𝑛 𝑖)=𝑛⋅(𝑛− 1) ⋅…⋅(𝑛−𝑖+ 1) 𝑖!=𝑛⋅𝑀≡0(mod 𝑛), donde 𝑀∈ℤ, ya que (𝑖!) ∤ 𝑛para 𝑖 > 1, para 𝑖= 1 se tiene trivialmente. Entonces (𝑛 𝑖)≡0(mod 𝑛) para todo 0< 𝑖 < 𝑛. Sea 𝑛compuesto. Consideremos 𝑞un factor primo de su descomposición y sea 𝑞𝑘∥𝑛. Tenemos que (𝑛 𝑞)=𝑛⋅(𝑛− 1) ⋅…⋅(𝑛−𝑞+ 1) 𝑞! =𝑝𝛼1 1 ⋅𝑝𝛼2 2 ⋅…⋅𝑝𝛼𝑙 𝑙 ⋅(𝑛− 1) ⋅…⋅(𝑛−𝑞+ 1) 𝑞!, 26 primalidad Como tenemos que 𝑜𝑟(𝑝)>1por la observación 3.1, el grado de ℎ(𝑋)debe ser mayor que uno. Una vez sabemos esto, definiremos 𝑊como el conjunto de los residuos de los polinomios del conjunto 𝑃módulo (ℎ(𝑋), 𝑝). Es claro que 𝑊está generado como grupo multiplicativo por {𝑋, 𝑋 + 1, 𝑋 + 2,…, 𝑋 +𝑙}⊂𝔽=𝔽𝑝[𝑋]∕⟨ℎ(𝑋)⟩ y, por tanto, 𝑊se puede entender como un subgrupo de 𝔽∗. A continuación daremos una cota inferior para el cardinal del grupo 𝑊. Lema 3.6.En las condiciones anteriores, |𝑊|≥(𝑡+𝑙 𝑡−1). Demostración. Como ℎ(𝑋)es un factor del polinomio ciclotómico 𝑄𝑟(𝑋),𝑋es una raíz 𝑟-ésima de la unidad en 𝔽, pues ℎ(𝑋) ∣ 𝑄𝑟(𝑋)y en 𝔽,𝑄𝑟(𝑋)≡0. Ahora vamos a probar que dados cualesquiera dos polinomios distintos de grado menor que 𝑡en 𝑃, ambos se corresponden con elementos diferentes de 𝑊. Sean 𝑓(𝑋) y𝑔(𝑋)dos polinomios que cumplan las dos condiciones. Supongamos, por reducción al absurdo, que 𝑓(𝑋) = 𝑔(𝑋)en 𝔽y consideremos 𝑚∈𝐼. Tenemos, pues, 𝑓(𝑋)𝑚=𝑔(𝑋)𝑚en 𝔽. Como todo elemento de 𝐼es introspectivo para cada elemento de 𝑃, tenemos en particular que 𝑚es introspectivo para 𝑓y𝑔, y como ℎ(𝑋)divide a 𝑋𝑟− 1, tenemos 𝑓(𝑋𝑚) = 𝑔(𝑋𝑚)en 𝔽. Por lo tanto 𝑋𝑚es raíz del polinomio 𝑞(𝑌) = 𝑓(𝑌) − 𝑔(𝑌),∀𝑚∈𝐺. Como gcd(𝑚, 𝑟) = 1, ya que 𝐺es un subgrupo de (ℤ∕ℤ𝑟)∗, cada 𝑋𝑚es una raíz 𝑟-ésima de la unidad. De esta forma tendremos |𝐺|=𝑡raíces distintas de 𝑞(𝑌)en 𝔽. Sin embargo, el grado de 𝑞(𝑌)ha de ser menor que 𝑡debido a la elección de 𝑓y 𝑔. Pero esto es una contradicción con el hecho de que tiene 𝑡raíces distintas. Luego 𝑓(𝑋)≠𝑔(𝑋)en 𝔽. Sea entonces 𝑖≠𝑗en 𝔽𝑝con 1≤𝑖, 𝑗 ≤𝑙, siendo 𝑙=⌊√𝜙(𝑟)⋅log(𝑛)⌋<√𝑟log(𝑛)< 𝑟 y𝑝>𝑟. Entonces 𝑋, 𝑋 + 1, 𝑋 + 2,…, 𝑋 +𝑙son todos elementos distintos en 𝔽. Por otra parte, 𝑋+𝑎≠0en 𝔽, para todo 𝑎, con 0≤𝑎≤𝑙, pues el grado de ℎes mayor que 1. Por lo tanto existen al menos 𝑙+ 1 polinomios de grado uno en 𝑊. De esta forma, existen al menos (𝑡+𝑙 𝑡−1)polinomios distintos de grado menor que 𝑡en 𝑊. Luego concluimos que |𝑊|≥(𝑡+𝑙 𝑡−1). Ahora bien, en el caso de que 𝑛no sea potencia de un primo 𝑝, además de estar |𝑊|acotado inferiormente, también podemos acotarlo superiormente. 3. el algoritmo aks y su corrección 27 Lema 3.7.Si 𝑛no es potencia de 𝑝, entonces |𝑊|≤𝑛√𝑡. Demostración. Consideremos el subconjunto 𝐽 ⊆ 𝐼 dado por 𝐽={(𝑛 𝑝)𝑖 𝑝𝑗|||0≤𝑖, 𝑗 ≤⌊√𝑡⌋}. Si 𝑛≠𝑝𝑘para algún 𝑘, entonces 𝐽contiene (⌊√𝑡⌋+ 1)2 > 𝑡 números distintos, pues ⌊(√𝑡)2+ 2 ⋅√𝑡+ 1⌋> 𝑡. Como |𝐺|=𝑡, al menos dos elementos en 𝐽deben ser iguales módulo 𝑟, pues el número de elementos de 𝐽es mayor que el de 𝐺. Sean dichos números 𝑚1y𝑚2tal que 𝑚1> 𝑚2. Así, tenemos: 𝑋𝑚1≡𝑋𝑚2(mod 𝑋𝑟− 1). Sea 𝑓(𝑋) ∈ 𝑃. Entonces: 𝑓(𝑋)𝑚1≡𝑓(𝑋𝑚1)≡𝑓(𝑋𝑚2)≡𝑓(𝑋)𝑚2(mod 𝑋𝑟− 1,𝑝). Por lo que tenemos: 𝑓(𝑋)𝑚1≡𝑓(𝑋)𝑚2 en 𝔽. De esta forma, 𝑓(𝑋) ∈ 𝑊es una raíz del polinomio 𝑞(𝑌) = 𝑌𝑚1−𝑌𝑚2en 𝔽. Como hemos tomado 𝑓(𝑋)como un elemento arbitrario de 𝑊,𝑞(𝑌)ha de tener al menos ∣𝑊∣raíces distintas en 𝔽. Por lo tanto, el grado de 𝑞(𝑌)es 𝑚1, pero 𝑚1≤(𝑛 𝑝 ⋅𝑝)⌊√𝑡⌋≤𝑛√𝑡. Esto prueba que |𝑊|≤𝑛√𝑡. Una vez hemos probado estas cotas que estiman el tamaño de 𝑊, estamos listos para probar la corrección del algoritmo. Demostremos pues la implicación que falta. Lema 3.8.Si el algoritmo devuelve PRIME, entonces 𝑛es primo. Demostración. Supongamos pues que el algoritmo devuelve PRIME. Por 3.6, para 𝑡= |𝐺|y𝑙=⌊√𝜙(𝑟)⋅log(𝑛)⌋, tenemos: |𝑊|≥(𝑡+𝑙 𝑡− 1)≥(𝑙+1+⌊√𝑡log(𝑛)⌋ ⌊√𝑡log(𝑛)⌋) 28 primalidad pues 𝑡 > √𝑡⋅log(𝑛). Ahora bien, como 𝑙=⌊√𝜙(𝑟)⋅log(𝑛)⌋≥⌊√𝑡⋅log(𝑛)⌋: (𝑙+1+⌊√𝑡⋅log(𝑛)⌋ ⌊√𝑡⋅log(𝑛)⌋)≥(𝑙+1+⌊√𝑡⋅log(𝑛)⌋)⋅…⋅(𝑙+ 2) ⌊√𝑡⋅log(𝑛)⌋⋅…⋅2⋅1 ≥ ≥(2⋅⌊√𝑡⋅log(𝑛)⌋+ 1)⋅…⋅(⌊√𝑡⋅log(𝑛)⌋+ 2) ⌊√𝑡⋅log(𝑛)⌋⋅…⋅2⋅1 ≥(2⌊√𝑡⋅log(𝑛)⌋+ 1 ⌊√𝑡⋅log(𝑛)⌋) Teniendo en cuenta que ⌊√𝑡⋅log(𝑛)⌋>⌊log2(𝑛)⌋≥1, y haciendo uso de 2.3, se sigue: (2⌊√𝑡⋅log(𝑛)⌋+ 1 ⌊√𝑡⋅log(𝑛)⌋)>2⌊√𝑡⋅log(𝑛)⌋≥𝑛√𝑡, con lo que tenemos |𝑊|> 𝑛√𝑡. Por otra parte, por 3.7 sabemos que |𝑊|≤𝑛√𝑡, si 𝑛≠𝑝𝑘para algún 𝑘. Luego, ha de existir cierto 𝑘 > 0para el que se cumple 𝑛=𝑝𝑘. Pero si 𝑘 > 1el algoritmo devuelve COMPOSITE en el paso 1, por tanto 𝑘= 1. Entonces podemos concluir que 𝑛=𝑝y el algoritmo devuelve PRIME. Por tanto, gracias a los lemas 3.8 y3.2 hemos probado el teorema 3.1 que nos garantiza que el algoritmo devuelve PRIME si y sólo si 𝑛es primo. 4 Análisis de la complejidad En esta sección estudiaremos la complejidad del algoritmo. Para ello tendremos en cuenta, según puede observarse en [MCA], que: Sumar dos números binarios 𝑛y𝑚, donde la longitud de 𝑛es mayor a la de 𝑚, es (log(𝑛)), Multiplicar 𝑛por 𝑚tiene una complejidad de (log(𝑛) log(𝑚)), y Dividir 𝑛entre 𝑚tiene una complejidad de (log2(𝑛)). Además, la complejidad de estas operaciones entre un par de polinomios de grado 𝑡es de 𝑂(𝑡⋅log2(𝑛)). Sin embargo, en el artículo original se considera que la complejidad tanto de la suma como del producto y división de dos números binarios 𝑛y𝑚, siendo 𝑛el de mayor longitud, es  (log(𝑛)). Es más, debido a esto se observa que esas mismas operaciones entre dos polinomios de grado 𝑡con coeficientes del orden de (log(𝑛)) pueden ser realizadas en un tiempo de (𝑡⋅log(𝑛)). Debido a todo esto se enuncia el siguiente teorema: Teorema 4.1. La complejidad asintótica del algoritmo es  (log21∕2(𝑛)). La prueba de este teorema puede verse en [PinP]. Nosotros probaremos el siguiente teorema, análogo al anteriormente enunciado, bajo las condiciones expuestas al comienzo de la sección. Dicho teorema nos da una complejidad levemente mayor a la ya expuesta. Teorema 4.2. La complejidad del algoritmo es de (log23∕2(𝑛)). Demostración. El primer paso del algoritmo es: Si 𝑛=𝑎𝑏para ciertos 𝑎∈ℕy𝑏 > 1, entonces COMPOSITE. 30 primalidad Para comprobar que 𝑛es igual a 𝑎𝑏para ciertos 𝑎y𝑏debemos calcular aproximadamente 𝑏raíces para 𝑏≤log(𝑛). Lo que nos da una complejidad de [PPT] (log3(𝑛) log log log(𝑛)). Sin embargo, dicha complejidad puede mejorarse si en lugar de evaluar las 𝑏raíces comprobamos si 𝑛es una potencia perfecta módulo un primo pequeño. Luego podemos concluir que este paso se lleva a cabo en un tiempo de (log2(𝑛)) [PPT]. El segundo paso consiste en encontrar el menor 𝑟tal que 𝑜𝑟(𝑛)>log2(𝑛). La idea es probar con distintos valores de 𝑟e ir comprobando si se cumple que 𝑛𝑘≢1(mod 𝑟),∀𝑘≤log2(𝑛). En primer lugar, como se observa en [TCYC], sabemos que hacer 𝑎𝑛(mod 𝑚) tiene una complejidad de (log(𝑛) log2(𝑚)). En nuestro caso debemos calcular, para cada valor de 𝑟,𝑛𝑘(mod 𝑟), por tanto tenemos: (log(𝑘) log2(𝑟)). luego, en nuestro caso, como 𝑘≤log2(𝑛)tenemos que (log (log2(𝑛))log2(𝑛))=(log4(𝑛)). Además, por el lema 3.3, tenemos que sólo hay que probar, a lo más, con 𝑂(log5(𝑛)) valores diferentes de 𝑟. Por ende, la complejidad total de este paso será (log4(𝑛)⋅𝑟)=(log4(𝑛) log5(𝑛))=(log9(𝑛)). El tercer paso consiste en comprobar si 1<gcd(𝑎, 𝑛)< 𝑛 para algún 𝑎≤𝑟 y, en caso afirmativo, devolver COMPOSITE. En este caso, debemos hacer el máximo común divisor de 𝑟números a lo sumo, pues 𝑎≤𝑟. Para cada máximo común divisor debemos realizar (log(𝑛)) divisiones y, como cada división tiene una complejidad de (log2(𝑛)), concluimos que la complejidad de cada máximo común divisor es de (log(𝑛) log2(𝑛)) = (log3(𝑛)) [TCYC]. Por tanto la complejidad de este paso será de (𝑟⋅log3(𝑛))=(log5(𝑛)⋅log3(𝑛))=(log8(𝑛)), 4. análisis de la complejidad 31 por el lema 3.3. El cuarto paso consiste en verificar si 𝑛≤𝑟y, en caso afirmativo el algoritmo devolverá PRIME. Luego la complejidad es simplemente (log(𝑛)), pues he de hacer una única comprobación. En el quinto paso tenemos el bucle siguiente: Para 𝑎= 1 hasta ⌊√𝜙(𝑟) log(𝑛)⌋ Si (𝑋+𝑎)𝑛≢𝑋𝑛+𝑎(mod 𝑋𝑟− 1, 𝑛) Entonces COMPOSITE. En este paso debemos comprobar si se verifican ⌊√𝜙(𝑟) log(𝑛)⌋ecuaciones. En cada una de dichas ecuaciones necesitamos (log(𝑛)) multiplicaciones de grado 𝑟y coeficientes de tamaño (log(𝑛)) [PCR]. Luego, por un razonamiento similar al del paso 3 tenemos que resolver cada ecuación, lo que requiere una complejidad de (𝑟log(𝑛) log2(𝑛))=(𝑟log3(𝑛)). Además, como tenemos ⌊√𝜙(𝑟) log(𝑛)⌋ecuaciones, la complejidad de este paso será: (𝑟√𝜙(𝑟) log(𝑛) log3(𝑛))=(𝑟√𝜙(𝑟) log4(𝑛))=(𝑟3 2log4(𝑛)) =((log5(𝑛))3∕2 log4(𝑛))=(log23∕2(𝑛)), empleando el lema 3.3 y la definición de 𝜙(𝑟). Por tanto, podemos concluir que la complejidad del algoritmo ha de ser: (log2(𝑛))+(log9(𝑛))+(log8(𝑛))+(log(𝑛))+(log23∕2(𝑛)), esto es, (log23∕2(𝑛))). Los autores exponen que la complejidad del algoritmo puede ser disminuida si se mejora la estimación de 𝑟. De hecho, la cota óptima se dará cuando 𝑟=(log2(𝑛)) y, en este caso, la complejidad del algoritmo pasará a ser  (log6(𝑛)). Para ello se apoyan en dos conjeturas muy conocidas, la conjetura de Artin y la conjetura de densidad de primos de Sophie Germain, las cuales nosotros únicamente vamos a comentar, sin entrar en mucho detalle. La conjetura de Artin nos dice que dado cualquier 𝑛∈ℕtal que no es un cuadrado perfecto, el número de primos 𝑞≤𝑚tal que 𝑜𝑞(𝑛) = 𝑞− 1 es asintóticamente 32 primalidad 𝐴(𝑛)(𝑚∕ log(𝑛)), donde 𝐴(𝑛)es una constante denominada la constante de Artin. En el caso de que la conjetura fuese cierta lo único que se sabe acerca de dicha constante es que 𝐴(𝑛)>0.35. Los primos de (Sophie) Germain son aquellos primos 𝑞tal que 2𝑞+ 1 es también primo. La conjetura de densidad de primos de Germain afirma que el número de primos de Germain menores que 𝑚es asintóticamente 2𝐶2𝑚∕ log2(𝑚), donde 𝐶2es una constante denominada la constante de primos gemelos, que se estima que tenga un valor aproximado de 0.66. 5 Un ejemplo concreto En esta sección haremos, a partir de determinado número 𝑛, un seguimiento en profundidad del funcionamiento de nuestro algoritmo. Veremos lo que sucede explícitamente en cada paso para llegar finalmente a saber si 𝑛es o no primo. Consideremos 𝑛= 197. Primer paso Lo que nuestro algoritmo hace en primer lugar a la hora de enfrentarse al problema es tratar de encontrar un cierto 𝑎∈ℕy un cierto 𝑏 > 1tal que 𝑛= 197 = 𝑎𝑏. Si encuentra dichos valores devuelve COMPOSITE, en caso contrario llevamos a cabo el siguiente paso. Para ello, para cada valor de 𝑎debemos calcular log𝑎(197) (con un método numérico estándar), cuyo entero más próximo, si hay alguno razonablemente cerca, tomaremos como 𝑏, y luego comprobaremos si 𝑎𝑏= 197. Si se cumple dicha igualdad tenemos que 𝑛es compuesto. Si no, seguiremos el mismo procedimiento para el siguiente valor de 𝑎. Es claro que debemos realizar dichos cálculos para 𝑎 < √197 ≈ 14, pues 𝑎𝑏>197 para 𝑎 > 14 y𝑏 > 1. Veámoslo: En primer lugar, es claro que, 𝑎≠1. Luego razonemos para 𝑎≥2. Sea 𝑛= 197. Sea 𝑎= 2; Tenemos que log2(197) = 7.62. Pero 7.62 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 2𝑏= 197. Sea 𝑎= 3; 34 primalidad Tenemos que log3(197) = 4.80. Pero 4.80 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 3𝑏= 197. Sea 𝑎= 4; Tenemos que log4(197) = 3.81. Pero 3.81 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 4𝑏= 197. Sea 𝑎= 5; Tenemos que log5(197) = 3.28. Pero 3.28 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 5𝑏= 197. Sea 𝑎= 6; Tenemos que log6(197) = 2.94 ≈ 3. Pero 63= 216 ⇐⇒ No existe 𝑏tal que 6𝑏= 197. Sea 𝑎= 7; Tenemos que log7(197) = 2.71. Pero 2.71 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 7𝑏= 197. Sea 𝑎= 8; Tenemos que log8(197) = 2.54. Pero 2.54 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 8𝑏= 197. Sea 𝑎= 9; Tenemos que log9(197) = 2.40. Pero 2.40 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 9𝑏= 197. Sea 𝑎= 10; Tenemos que log10(197) = 2.29. Pero 2.29 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 10𝑏= 197. Sea 𝑎= 11; Tenemos que log11(197) = 2.20. Pero 2.20 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 11𝑏= 197. Sea 𝑎= 12; Tenemos que log12(197) = 2.12. Pero 2.12 no es próximo a un entero 𝑏⇐⇒ No existe 𝑏tal que 12𝑏= 197. Sea 𝑎= 13; Tenemos que log13(197) = 2.06 ≈ 2. Pero 132= 169 ⇐⇒ No existe 𝑏tal que 13𝑏= 197. 5. un ejemplo concreto 35 Sea 𝑎= 14; Tenemos que log14(197) = 2.00. Pero 142= 196 ⇐⇒ No existe 𝑏tal que 14𝑏= 197. Por tanto no existe ningún 𝑎∈ℕni 𝑏 > 1tal que 𝑎𝑏= 197. Luego pasamos al siguiente paso. Este paso lo hemos hecho por inspección, pero en la práctica habría que usar un algoritmo más eficaz tipo [DPP]. Tras realizar los cálculos de este paso con SAGE, observamos que emplea un tiempo de 6.11ms. Segundo paso Ahora debemos encontrar el menor 𝑟tal que 𝑜𝑟(𝑛)>log2(𝑛), es decir, el menor 𝑟 que verifique que el primer 𝑘 > 0con 197𝑘≡1(mod 𝑟) cumpla 𝑘 > log2(197) ≈ 58.09. Así pues, el 𝑟que buscamos ha de satisfacer que 𝑜𝑟(197) >log2(197) ≈ 58.09. Como 𝑜𝑟(𝑛)|#(ℤ∕ℤ𝑟)∗=𝜙(𝑟), necesitamos que 𝑟sea tal que |𝜙(𝑟)|>58. Comencemos pues con 𝑟= 59, pues es claro que para 𝑟≤58 no se cumple dicha propiedad. Veámoslo: Sea 𝑟= 59. Como 𝜙(59) = 58, Sus divisores son 1,2,29,58; Luego basta probar con 2y29 Si 𝑘= 2,1972= 46 (mod 59). Si 𝑘= 29,19729 = 1 (mod 59). Pero 29 <log2(197). Sea 𝑟= 60. Como 𝜙(60) <58,𝑜60(197) <58.09. Sea 𝑟= 61. Como 𝜙(61) = 60, Sus divisores son 1,2,3,4,5,6,10,12,15,20,30,60; 42 primalidad Luego no se devuelve COMPOSITE. Si 𝑎= 37; (𝑋+ 37)197 ≡𝑋197 + 37 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 38; (𝑋+ 38)197 ≡𝑋197 + 38 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 39; (𝑋+ 39)197 ≡𝑋197 + 39 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 40; (𝑋+ 40)197 ≡𝑋197 + 40 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 41; (𝑋+ 41)197 ≡𝑋197 + 41 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 42; (𝑋+ 42)197 ≡𝑋197 + 42 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 43; (𝑋+ 43)197 ≡𝑋197 + 43 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 44; (𝑋+ 44)197 ≡𝑋197 + 44 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 45; (𝑋+ 45)197 ≡𝑋197 + 45 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 46; (𝑋+ 46)197 ≡𝑋197 + 46 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. 5. un ejemplo concreto 43 Si 𝑎= 47; (𝑋+ 47)197 ≡𝑋197 + 47 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 48; (𝑋+ 48)197 ≡𝑋197 + 48 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 49; (𝑋+ 49)197 ≡𝑋197 + 49 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 50; (𝑋+ 50)197 ≡𝑋197 + 50 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 51; (𝑋+ 51)197 ≡𝑋197 + 51 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 52; (𝑋+ 52)197 ≡𝑋197 + 52 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 53; (𝑋+ 53)197 ≡𝑋197 + 53 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 54; (𝑋+ 54)197 ≡𝑋197 + 54 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 55; (𝑋+ 55)197 ≡𝑋197 + 55 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 56; (𝑋+ 56)197 ≡𝑋197 + 56 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 57; (𝑋+ 57)197 ≡𝑋197 + 57 (mod 𝑋67 − 1,197) 44 primalidad Luego no se devuelve COMPOSITE. Si 𝑎= 58; (𝑋+ 58)197 ≡𝑋197 + 58 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 59; (𝑋+ 59)197 ≡𝑋197 + 59 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 60; (𝑋+ 60)197 ≡𝑋197 + 60 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Si 𝑎= 61; (𝑋+ 61)197 ≡𝑋197 + 61 (mod 𝑋67 − 1,197) Luego no se devuelve COMPOSITE. Por lo tanto no podemos concluir que 𝑛sea compuesto, luego aplicamos el paso 6. Tras realizar los cálculos de este paso con SAGE, observamos que emplea un tiempo de 9.08ms. Sexto paso. Finalmente concluimos que 𝑛es primo y, por ende, el algoritmo devuelve PRIME. Es evidente que esta no es una implementación optimizada, pues el tiempo necesario para determinar si 𝑛es primo es muy elevado. Es más, es claro que el quinto paso es el que más tiempo consume pues depende del valor de 𝑟(a mayor 𝑟, más iteraciones deberemos realizar y por tanto dicho paso consumirá un tiempo mayor). Esto hace que el algoritmo, en la práctica, puede no ser muy útil para números considerablemente grandes. Bibliografía [PinP] M. AGRAWAL, N. KAYAL, N. SAXENA, Primes is in P. Annals of Mathematics, 160 (2004), 781–793. [PCR] M. AGRAWAL, S. BISWAS, Primality and identity testing via Chinese remaindering. Journal of the ACM 50 (2003), 429–443. [PPT] BACH, E., SORENSON, J. Sieve algorithms for perfect power testing. Algorithmica 9(1993), 313–328. [DPP] D.J. BERNSTEIN, Detecting perfect powers in essentially linear time. Mathematics of Computation 67 (1998), 1253-1283. [BFE] F. BORNEMANN, Primes is in P: A Breakthrough for "Everyman". Notices of the AMS, May 2003. [TCYC] Dpto. de Álgebra (US), Notas deTeoría de Códigos y Criptografía. Universidad de Sevilla. [TAN] Dpto. de Análisis Matemático (US), Notas de Teoría Analítica de Números. Universidad de Sevilla. [FFA] R. LIDL, H. NIEDERREITER, Introduction to Finite Fields and their Applications. Cambridge Univ. Press, Cambridge, 1986. [CIP] M. NAIR, On Chebyshev-type inequalities for primes. Amer. Math. Monthly 89 (1982), 126–129. [MCA] J. VON ZUR GATHEN, J. GERHARD, Modern Computer Algebra. Cambridge Univ. Press, Cambridge, 1999.