Tests probabilísticos de primalidad

TESTS PROBABIL´ ISTICOS DE PRIMALIDAD J´ulia Bujosa Moya Facultad de Matem´aticas Departamento de ´ Algebra J´ulia Bujosa Moya Esta memoria se presenta como parte de los criterios exigidos para completar los requisitos y obtener el t´ıtulo del Grado en Matem´aticas concedido por la Universidad de Sevilla. Tutorizada por Jos´e Mar´ıa Tornero S´anchez Departamento de ´ Algebra Junio 2024, Sevilla Para empezar dir´e que es el final. No es un final feliz, tan s´olo es un final. Resumen La idea de este trabajo es determinar la primalidad de un n´umero a partir de tests que buscan ganar eficiencia arriesgando eficacia. Pese a que suelen usarse como sin´onimos, la eficiencia hace referencia a utilizar algoritmos con un menor coste computacional, sin embargo, la eficacia hace referencia a un resultado m´as correcto y preciso sin tener en cuenta los recursos usados. Realmente este trabajo presenta tests que buscan un equilibrio de ambas, al que podemos llamar efectividad. La manera de trabajar de estos tests es tratar de verificar ciertas propiedades que sabemos que cumplen los n´umeros primos. Y es en la definici´on de estas propiedades donde aparecen los distintos tipos de pseudoprimos, n´umeros compuestos jugando a ser primos, es decir, n´umeros que tambi´en cumplen las propiedades testadas. En el primer cap´ıtulo damos unas primeras nociones que combinadas con algunos resultados generales ser´an herramientas base para construir los tests que iremos presentando a posteriori. A lo largo del segundo cap´ıtulo, introducimos el primer test probabil´ıstico, el Test de Fermat, basado propiamente en el Peque˜no Teorema de Fermat. Con ´el aparece por primera vez una familia de pseudoprimos. Precisamente su existencia hace que este test no sea lo eficaz que se desea y motiva la b´usqueda de propiedades y tests alternativos. Adem´as, este primer tipo de pseudoprimos, y su versi´on fuerte, llamados n´umeros de Carmichael, toman un papel hist´oricamente muy importante en la b´usqueda de tests de primalidad por lo que dedicamos una secci´on para su estudio. En el tercer cap´ıtulo exponemos el test probabil´ıstico de Solovay–Strassen, basado en el Teorema de Euler, dando pie a los pseudoprimos de Euler. Para la implementaci´on del test se introducen los s´ımbolos de Legendre y Jacobi. Este ´ultimo no necesita factorizaciones para ser calculado y dada su importancia en la eficacia del test, se introduce una secci´on profundizando en el c´alculo efectivo del mismo. Siguiendo el orden cronol´ogico, en el cuarto cap´ıtulo introducimos un test probabil´ıstico que super´o en efectividad al de Solovay–Strassen, el test de Miller Rabin, basado en una propiedad curiosa de los primos que cumplen tambi´en los llamados pseudoprimos fuertes. Siguiendo la intuici´on que nos acompa˜na durante el trabajo, estos n´umeros son a´un menos frecuentes que los pseudoprimos de Euler, lo que hace tener a nuestro ´ultimo test menor probabilidad de error que todos los tests estudiados antes. Por ´ultimo, se presentan los pseudoprimos de Lucas respectivos a un par de par´ametros tal que haciendo una buena elecci´on de estos, parecen no solaparse con los dem´as pseudoprimos vistos (problema que sigue abierto). De aqu´ı nace el ´ultimo test descrito en esta memoria, que recibe el nombre de Baillie-PSW, y el cual resulta infalible por el momento, aunque su correcci´on depende de una conjetura. Abstract The aim of this work is to determine the primality of a number using tests that seek to balance efficiency and effectiveness. Although these terms are often used interchangeably, efficiency refers to using algorithms with lower computational costs, while effectiveness refers to obtaining more accurate and precise results without considering the resources used. In reality, this work presents tests that aim for a balance of both, which we can call effectiveness. The way these tests work is by trying to verify certain properties that we know prime numbers satisfy. It is in the definition of these properties that different types of pseudoprimes appear, composite numbers pretending to be prime, that is, numbers that also satisfy the tested properties. In the first chapter, we provide some initial concepts that, combined with some general results, will be basic tools for constructing the tests we will present later. In the second chapter, we introduce the first probabilistic test, the Fermat Test, which is based on Fermat’s Little Theorem. With it, a family of pseudoprimes appears for the first time. The existence of these pseudoprimes makes this test not as effective as desired and motivates the search for alternative properties and tests. Additionally, this first type of pseudoprimes, and their stronger version called Carmichael numbers, play a historically important role in the search for primality tests, so we dedicate a section to their study. In the third chapter, we present the probabilistic Solovay-Strassen test, based on Euler’s Theorem, giving rise to Euler pseudoprimes. For the implementation of the test, the Legendre and Jacobi symbols are introduced. The latter does not require factorizations to be calculated, and given its importance in the test’s effectiveness, we include a section delving into its effective calculation. Following the chronological order, in the fourth chapter, we introduce a probabilistic test that surpassed the Solovay-Strassen test in effectiveness, the Miller-Rabin test, based on a curious property of primes that also satisfies the so-called strong pseudoprimes. Following the intuition that guides us throughout the work, these numbers are even less frequent than Euler pseudoprimes, which gives our last test a lower probability of error than all the tests studied before. Finally, the Lucas pseudoprimes corresponding to a pair of parameters are presented. With a good choice of these parameters, they seem not to overlap with the other pseudoprimes seen (a problem that remains open). From this arises the last test described in this report, called the Baillie-PSW test, which is infallible for now, although its correctness depends on a conjecture. ´ Indice Introducci´on 2 1. En busca de la primalidad 4 1.1. Primerasnociones ............................. 4 1.2. Resultados generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Test de Fermat 9 2.1. Pseudoprimos de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2. N´umeros de Carmichael . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3. Test de Solovay–Strassen 18 3.1. Pseudoprimos de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2. C´alculo efectivo del s´ımbolo de Jacobi . . . . . . . . . . . . . . . . . . 25 4. Test de Miller–Rabin 31 5. Test de Baillie-PSW 41 5.1. Pseudoprimos de Lucas . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2. Ejemplo de aplicaci´on con SageMath ................... 47 Ap´endice: Implementaci´on en SageMath 48 5.2.1. Elecci´on de niconSageMath ................... 48 5.2.2. Primalidad de nicon Solovay-Strassen . . . . . . . . . . . . . . 48 5.2.3. Primalidad de nicon Miller-Rabin . . . . . . . . . . . . . . . . 49 5.2.4. Primalidad de nicon Baillie-PSW . . . . . . . . . . . . . . . . 51 5.2.5. Ejemplo pseudoprimo de Lucas . . . . . . . . . . . . . . . . . . 52 5.2.6. C´alculo de π(x) con xentre 1010 y 2,5×1010 utilizando el algoritmo de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . 53 Bibliograf´ıa 54 1 1.2. RESULTADOS GENERALES Este resultado es de gran relevancia con respecto a los n´umeros primos, pese a no haber sido demostrado a´un. Tanto es as´ı que un gran n´umero de enunciados se han probado asumiendo que es cierto. En pocas palabras, lo que Riemann descubri´o que la distribuci´on de los ceros de la funci´on zeta de Riemann est´a ´ıntimamente relacionada con la distribuci´on de los n´umeros primos, revelando una conexi´on profunda y una dualidad entre ambos conceptos. Esta revelaci´on sugiere que no existe una f´ormula o patr´on simple que prediga la distribuci´on de los n´umeros primos. Es esto lo que nos motiva a seguir construyendo algoritmos que nos ayuden a determinar la primalidad de un n´umero. Entremos en el asunto. Cap´ıtulo 2 Test de Fermat Vous me demandez si le nombre 100.895.598.169 est premier ou non, et une m´ethode pour d´ecouvrir, dans l’espace cun jour, s’il est premier ou compos´e. A cette question, je r´eponds que ce nombre est compos´e et se fait du produit de ces deux: 898.423 et 112.303, qui sont premiers. Pierre de Fermat [12] 2.1. Pseudoprimos de Fermat A mediados del siglo XVII, el matem´atico franc´es Pierre de Fermat escribi´o una carta a su amigo y confidente Fr´enicle de Bessy, en la que expon´ıa lo que m´as tarde se conocer´ıa como su Peque˜no Teorema [8], que no es m´as que el Teorema de Euler 1.10 aplicado a los primos. Teorema 2.1 (Peque˜no Teorema de Fermat) Sea pun n´umero primo y aun entero tal que gcd(a, p) = 1. Entonces, ap−1≡1 (m´od p) (2.1) Este resultado es la base de los tests que veremos m´as adelante. La pregunta clave es la siguiente: ¿ser´ıa cierto el rec´ıproco? Si as´ı fuera, el siguiente test, basado en la comprobaci´on de (2.1), ser´ıa la soluci´on al problema de la primalidad. Entrada: (n, k)∈N≥3×N, con nimpar y kuna cota para el n´umero de iteraciones Salida: False, si nes compuesto, o bien npasa el test. 9 2.1. PSEUDOPRIMOS DE FERMAT Algorithm 1 Test de primalidad de Fermat (kiteraciones) Entrada: (n, k)∈N≥3×N, con nimpar y kuna cota para el n´umero de iteraciones Salida: False, si nes compuesto, o bien npasa el test. 1: i←0 2: while i<kdo 3: Elegir a∈Z/nZ\{0} 4: if gcd(a, n)= 1 then 5: return False 6: else 7: if an−1≡ 1 (m´od n)then 8: return False 9: else 10: i←i+ 1 11: end if 12: end if 13: end while 14: return npasa el test Observaci´on 2.2 En caso de que el algortimo finalizara en la l´ınea 5 u 8, la base a que estamos testando ser´ıa nuestro testigo de composici´on. Observaci´on 2.3 Cabe remarcar que el algoritmo es eficiente. El paso 4 consiste en calcular el m´aximo com´un divisor de dos n´umeros, lo cual se puede hacer usando el algoritmo de Euclides con complejidad O(log3(n)) [10]. El paso 7 requiere la denominada exponenciaci´on modular. Para llevar a cabo esto, existe un m´etodo eficiente, el algoritmo de cuadrados repetidos, que consiste en trabajar con el exponente en base 2 e ir calculando cuadrados m´odulo nen funci´on de dicha descomposici´on del exponente. Con este m´etodo hallar an−1m´od ntiene complejidad O(log(n) log2(a)) [10], es decir, polinomial tanto en el tama˜no de acomo en el de n. Sin embargo, no todo es tan sencillo como parece y es este el punto cr´ıtico a partir del cual nace la motivaci´on del trabajo. El Peque˜no Teorema de Fermat proporciona una condici´on necesaria, no suficiente, para los n´umeros primos. Efectivamente, el rec´ıproco del teorema no es cierto, en general, puesto que aparecen n´umeros compuestos que pasan el test, es decir, podr´ıan ser err´oneamente identificados como primos. Veamos qui´enes son estos n´umeros y su importancia dentro del campo de la primalidad. 2.2. N´ UMEROS DE CARMICHAEL Definici´on 2.4 Sea n∈Z≥1, y aun n´umero tal que gcd(a, n) = 1, entonces se dice que nes un pseudoprimo (de Fermat) respecto de la base asi: an−1≡1 (m´od n).(2.2) Por ejemplo, para n= 91 = 7 ·13 y a= 3, efectivamente se cumple la equivalencia 390 ≡1 (m´od 91). Eso es, 91 es pseudoprimo respecto de la base 3. Sin embargo, 290 ≡40 (m´od 91), es decir, 91 no es pseudoprimo respecto de la base 2, por lo tanto el test detectar´ıa que nes compuesto y 2 ser´ıa un testigo de composici´on. Esto no ocurre con 1105 = 5 ·13 ·17, ya que es pseudoprimo tanto para la base 2 como para la base 3, de hecho lo es para toda base. Este ´ultimo ejemplo da lugar a una nueva definici´on que juega un papel realmente relevante en el campo de la primalidad. En efecto, los n´umeros de Carmichael definidos a continuaci´on, incitaron a los investigadores a buscar propiedades que cumplan los n´umeros primos distintas a (2.2). 2.2. N´umeros de Carmichael Definici´on 2.5 Un entero ncompuesto se dice que es un n´umero de Carmichael si es pseudoprimo respecto a toda base, es decir, an−1≡1 (m´od n)∀a∈Zcon 0 < a < n, gcd(a, n) = 1 (2.3) Veamos algunos ejemplos de n´umeros de Carmichael con propiedades que iremos explotando a medida que avanzamos en el campo de la pseudoprimalidad. Algunos de estos los hemos sacado de [27]. En concreto: 561 = 3 ·11 ·17,2821 = 7 ·13 ·31,15841 = 7 ·31 ·73 son n´umeros de Carmichael. Es importante hacer notar el n´umero de factores primos que poseen, ya que m´as adelante veremos una cota inferior de este n´umero. Veamos qu´e ocurre si aplicamos el test de Fermat al ´ultimo ejemplo. Esta sesi´on SAGE y todas las posteriores se encuentran recopiladas en el Ap´endice. 1def fermat_test (n , k): 2for _in range (k): 3a = randint (2, n - 2) 4if power_mod (a , n - 1, n) != 1: 5print (n , "es compuesto y falla el test en la iteracion ", i , "con la base ", a) 6return False 2.2. N´ UMEROS DE CARMICHAEL 7print (n , "es probablemente primo y pasa el test tras ", k, " iteraciones ") 8return True 9 10 fermat_test (15841 , 20) 11 OUT: 12 15841 es probablemente primo y pasa el test tras 20 iteraciones Lo cual es err´oneo como hemos aclarado arriba. ¿Podr´ıa implementarse este test como un algoritmo efectivo de primalidad salvo por la posibilidad de que el n´umero evaluado nsea un n´umero de Carmichael? Si nos ponemos en el mejor de los casos, y suponemos que nno es un n´umero de Carmichael y tampoco es un n´umero primo, entonces para estudiar la eficacia del test de Fermat, nos debemos preguntar para cu´antas bases podr´ıa nser pseudoprimo. De hecho, como veremos, se puede demostrar que, en esas condiciones, nes pseudoprimo respecto de menos de la mitad de las posibles bases a. Lema 2.6 Sea n∈Z≥2compuesto. El conjunto H=a∈Un|an−1= 1 es un subgrupo de Un. Demostraci´on: Para demostrar que Hes un subgrupo de Un, verificamos las dos condiciones usuales: 1. El producto es cerrado: Sean a, b ∈H. Esto implica que an−1= 1 y bn−1= 1 (por definici´on de H). Entonces, (ab)n−1=an−1bn−1= 1 ·1 = 1 (m´od n), lo que significa que ab ∈H. 2. Elemento inverso: Para cada a∈H, queremos probar que a−1∈H. Sabemos que an−1≡1 m´od n(por definici´on de H), entonces a−1=an−2y an−2n−1=an−1n−2≡1n−2≡1 m´od n, por lo tanto a−1∈H. Luego Hes un subgrupo de Un.□ Teorema 2.7 Si nno es un n´umero de Carmichael (es decir, no verifica (2.2) para alguna base a∈Un), entonces nno verifica (2.2) para al menos la mitad de las posibles bases a∈Un. 2.2. N´ UMEROS DE CARMICHAEL Demostraci´on: Sea Hel subgrupo definido en el lema anterior, y notemos h=|H| ym=|Un|=φ(n). Por el Teorema de Lagrange [8], sabemos que hdivide a m, es decir, que existe un d∈Ntal que dh =m. Al no ser nun n´umero de Carmichael tenemos que h < m, y entonces d≥2, por tanto h≤m/2. □ En consecuencia, suponiendo que nno es un n´umero de Carmichael, si el output del Test de Fermat es npasa el test,nser´a compuesto con una probabilidad menor que 1/2, es decir, el test falla con probabilidad inferior al 50 %. Si realizamos kiteraciones, la probabilidad de que npase todos los tests sin ser primo es entonces inferior a 1/2k. Como el algoritmo solo se puede considerar preciso bajo la condici´on de que nno sea un n´umero de Carmichael, necesitamos averiguar un poco m´as sobre estos curiosos n´umeros. En 1899 Korselt, en respuesta al Probl`eme Chinois de L’interm´ediaire des Math´ematiciens1, demostr´o el siguiente resultado. Teorema 2.8 (Korselt [20]) Sea nun entero compuesto. Las dos condiciones siguientes son equivalentes: 1. El entero nes un n´umero de Carmichael. 2. El entero nes libre de cuadrados y para todo primo pque divide a n, se cumple que (p−1) |(n−1). Demostraci´on: Sea nun n´umero de Carmichael y puno de sus divisores primos. En primer lugar veamos que nes libre de cuadrados. Es claro que existe una descomposici´on de ntal que n=pk·m, donde pes primo, k≥1 y gcd(p, m) = 1. Demostramos que k= 1 por reducci´on al absurdo. Supongamos que k > 1, caso en el que p2|n. Por el Teorema Chino del Resto, existe un ´unico a∈Z/nZtal que a≡1 + p(m´od pk), a ≡1 (m´od m). En ese caso gcd(a, n) = 1, de modo que por ser nun n´umero de Carmichael se tiene an−1≡1 (m´od n) y por tanto, (1 + p)n−1≡1 (m´od p2). 1Peri´odico franc´es fundado en 1894 y equivalente en esa ´epoca al actual The American Mathematical Monthly. 2.2. N´ UMEROS DE CARMICHAEL El Teorema del Binomio garantiza (1 + p)n−1≡1+(n−1)p(m´od p2), pero como n−1≡ −1 (m´od p2), se verifica (1 + p)n−1≡1−p(m´od p2). En consecuencia, se obtiene 1 ≡1−p(m´od p2), que es claramente un absurdo. Por ello, solo es posible que k= 1 y nsea libre de cuadrados. Veamos ahora que (p−1) |(n−1). Como nes libre de cuadrados, gcd(n/p, p) = 1. Sea bun elemento de Fpque sea generador de Up. El Teorema Chino del Resto garantiza que existe un ´unico a∈Z/nZtal que a≡b(m´od p), a ≡1 (m´od n/p). Estas condiciones nos garantizan que ap−1≡1 tanto en m´odulo pcomo en m´odulo n/p. Por tanto, de nuevo por el Teorema Chino del Resto, ap−1≡1 (m´od n), y por ser nun n´umero de Carmichael debe tenerse que (p−1) |(n−1). Probemos entonces que la condici´on (2) implica que nes de Carmichael. Sea entonces n > 2 un entero compuesto y libre de cuadrados tal que (p−1) |(n−1) para cada pprimo divisor de n. Dado a∈Un, el Peque˜no Teorema de Fermat garantiza que ap−1≡1 (m´od p), para todo pdivisor primo de n. Por lo tanto, se cumple que an−1≡1 (m´od p). En consecuencia, an−1≡1 (m´od n), resultando que nes un n´umero de Carmichael. □ Proposici´on 2.9 Si nes un n´umero de Carmichael, entonces tiene al menos tres factores primos distintos. Demostraci´on: Como nes de Carmichael, nno es primo, luego tiene al menos dos factores distintos, pues nes libre de cuadrados. Veamos que no puede tener s´olo dos. Si fuera el caso, ser´ıa n=pq, con p=q. Entonces, n−1 = pq −1 = (p−1)q+ (q−1). Por otro lado, (p−1) |(n−1) por ser de Carmichael, luego (p−1) |(q−1). De la misma forma, (q−1) |(p−1) y se tiene p=q, lo que no es posible. □ Despu´es de analizar estos n´umeros nos invade la duda de si realmente son tan importantes como para tenerlos en cuenta a la hora de testar la primalidad de un 2.2. N´ UMEROS DE CARMICHAEL n´umero ¿Cu´antos n´umeros de Carmichael menores que un x∈Zdado existen? ¿Hay infinitos n´umeros de Carmichael? En caso afirmativo, ¿con qu´e frecuencia encontramos n´umeros de Carmichael entre los n´umeros naturales? En otras palabras, ¿podemos comparar el crecimiento de los n´umeros de Carmichael con alguna funci´on conocida como hacemos con π(x) en el teorema de n´umeros primos? Para analizar heur´ısticamente este fen´omeno, denotaremos en lo sucesivo, C(x)=#n≤x|nes de Carmichael. Si tomamos x= 1016 para ver un ejemplo orientativo de la densidad de los n´umeros de Carmichael, tenemos por ejemplo C(x) = 246683 ≈2,5·105, π(x) = 279238341033925 ≈2,8·1014. El trabajo de Alford, Pomerance y Granville [1], involucrando a la vez t´ecnicas computacionales y sutiles argumentos de teor´ıa anal´ıtica de n´umeros, prueba que hay infinitos n´umeros de Carmichael aunque es cierto que son menos frecuentes que los primos. Aun as´ı, no son tan poco frecuentes como para ignorarlos. En la Tabla 1 (ver m´as adelante) se muestra una comparativa. Es m´as, se puede demostrar un resultado an´alogo al Teorema de los N´umeros Primos. Teorema 2.10 ([26]) En las condiciones anteriores, sea L(x) = exp −log(x) log log log(x) log log x Entonces, para xsuficientemente grande, se tiene que x2/7≪C(x)≪xL(x). Pese a que no sea el tema principal y los detalles de la prueba se queden fuera del alcance de este trabajo, vemos oportuno dar una idea de la prueba de este teorema, el cual resulta un an´alogo al Teorema de los N´umeros Primos. La cota superior fue sugerida por ¨ Erdos y se puede ver una prueba en [28]. Damos una idea de la demostraci´on de la prueba que proporcionaron Alford, Pomerance y Granville en [1] para la cota inferior (que prueba la existencia de infinitos n´umeros de Carmichael). La demostraci´on parte de la funci´on ψ:R2−→ N (x, y)7−→ #n∈Z|nes primo, n|kpara alg´un k≤x, n ≤y y de tres resultados principales que mencionamos a continuaci´on. El primero es el Lema de De Bruijn [6] el cual proporciona una estimaci´on precisa de la funci´on ψ(x, y) en t´erminos de xeycuando xes lo suficientemente grande en relaci´on con y. 2.2. N´ UMEROS DE CARMICHAEL Lema 2.11 (De Bruijn) Para cada ε > 0, existe un x0(ε) tal que si x > x0(ε), ln x≤y≤x, y u= ln x/ ln y, entonces ψ(x, y)≤x·exp (−(1 −ε)uln u). Adem´as, la demostraci´on hace uso del teorema de Rosser [33], el cual establece una relaci´on fundamental entre los n´umeros primos y el logaritmo natural, proporcionando l´ımites superiores e inferiores precisos para el n-´esimo n´umero primo: Teorema 2.12 (Rosser) Sea {Pn}n≥1la sucesi´on de los n´umeros primos. Para todo n´umero natural nse verifica que nln(n)< Pn<2nln(n). Y como ´ultimo resultado principal se apoya en la F´ormula de Abel [11], muy importante en Teor´ıa An´alitica de N´umeros. Teorema 2.13 (F´ormula de Abel) Para cada funci´on aritm´etica an, definimos A(x) = X n≤x a(n), donde A(x) = 0 si x < 0. Supongamos que f(x) tiene una derivada continua en el intervalo [x, y], con 0 < x < y. Entonces, X x≤n≤y a(n)f(n) = A(y)f(y)−A(x)f(x)−Zy x A(t)f′(t)dt La prueba del teorema se basa entonces en dividir los n´umeros de Carmichael n≤xen tres clases con 0 < δ < 1. En concreto: 1. Los que verifican n≤x1−δ. 2. Los que verifican x1−δ< n ≤xyntiene un factor primo p≥xδ. 3. Los que verifican x1−δ< n ≤xy todo factor primo de nes menor que xδ. El siguiente objetivo es encontrar una cota superior para cada una de estas clases. La construcci´on y demostraci´on de estas cotas implican el uso de herramientas y lemas adicionales, cuya exposici´on detallada requerir´ıa un trabajo aparte. La tabla de la siguiente p´agina (ver [17]) muestra la evoluci´on de C(x). Se a˜nade la ´ultima columna (extra´ıda de [14]) con el prop´osito de hacer notar la diferencia de densidades de primos y n´umeros de Carmichael. 2.2. N´ UMEROS DE CARMICHAEL Dadas las limitaciones del Test de Fermat causadas por la presencia de estos n´umeros tan especiales y que desgraciadamente no pasan desapercibidos, en los pr´oximos cap´ıtulos abordaremos otros tests de primalidad probabil´ısticos que superan el problema de la existencia de n´umeros de Carmichael y ofrecen un funcionamiento m´as fiable, a la par que eficiente. x C(x) A˜no Descubridor(es) π(x) 1031 1910 Carmichael 168 1047 1912 Carmichael 1229 10516 9592 10643 78498 107105 664579 108255 1938 Poulet 5761455 109646 1975 Swift 50847534 1010 1547 455052511 2.5 ×1010 2163 1980 Pomerance, Selfridge, Wagstaff21099985405 1011 3605 4118054813 1012 8241 1990 Jaeschke 37607912018 1013 19279 346065536839 1014 44706 3204941750802 1015 105212 1992 Pinch 29844570422669 2Calculado en la secci´on 5.2. 3.1. PSEUDOPRIMOS DE EULER Estamos en condiciones de introducir el Test de Solovay–Strassen, algoritmo probabil´ıstico que conduce o a la conclusi´on de que nes compuesto o a la conclusi´on de que es probablemente primo. El algoritmo se va a basar simplemente en escoger una base 0 < a < n y ver qu´e ocurre con la congruencia a(n−1)/2≡a n(m´od n). Si npasa el test para la base a, no se puede asegurar que nsea primo, hasta que probemos con todos los a∈Un. Ahora bien, lo que hemos mejorado eliminando la posibilidad de que entren en juego los n´umeros de Carmichael es la probabilidad de error, ya que si nes compuesto, Pnpasa el test≤1 2k con kel n´umero de veces que repetimos el algoritmo para diferentes bases. Algorithm 2 Test de primalidad de Solovay–Strassen (kiteraciones) Entrada: (n, k)∈N≥3×N, con nimpar y kuna cota para el n´umero de iteraciones Salida: False, si nes compuesto, o bien npasa el test 1: i←0 2: while i<kdo 3: Elegir a∈Z/nZ 4: if gcd(a, n)= 1 then 5: return False 6: else 7: if a(n−1)/2≡ a n(m´od n)then 8: return False 9: else 10: i←i+ 1 11: end if 12: end if 13: end while 14: return npasa el test Observaci´on 3.13 En cuanto a complejidad, encontrar el lado derecho a(n−1)/2toma O(log3n) operaciones de bits, utilizando el m´etodo de exponenciaci´on modular que mencionamos en el cap´ıtulo anterior. Lo que resulta novedoso y beneficioso a la par es la complejidad de calcular el s´ımbolo de Jacobi en el lado izquierdo. Parece que el s´ımbolo de Jacobi exige factorizar npara verificar la igualdad, pero no es as´ı. De hecho se introduce este nuevo concepto porque para su c´alculo, en caso de que no sepamos si nes primo o no, podemos calcularlo sin factorizar n, tarea que habr´ıa 3.2. C´ ALCULO EFECTIVO DEL S´ IMBOLO DE JACOBI resultado incluso m´as compleja que determinar su primalidad. Aunque haremos ´enfasis en esto en la siguiente secci´on, adelantamos que el segundo lado de la igualdad tambi´en toma O(log3n) operaciones de bits. Luego siendo kel n´umero de veces que repetimos el algoritmo, este tiene complejidad O(klog3n). Por tanto vemos que es un algoritmo eficiente, aunque eso s´ı, probabil´ıstico. Como hemos comentado ya, se ha implementado en el ap´endice una versi´on de cada test que presentaremos en este trabajo, tomando 3 ejemplos de la misma magnitud pero con caracter´ısticas distintas para probar los tests sobre ellos. Dejamos los c´alculos en el ap´endice mostrando ´unicamente los resultados, que como vemos nos dan, cuando procede, testigos de composici´on: 12432902008176640000 es compuesto y falla el test en la i t e r a c i n 1 con 2la base 1868969210451108746 33044260448006092643 es compuesto y falla el test en la i t e r a c i n 1 con 4la base 2680792065180999020 51816787885244115403 es probablemente primo y pasa el test tras 20 6iteraciones 3.2. C´alculo efectivo del s´ımbolo de Jacobi Como se ha introducido anteriormente, al igual que el Algoritmo de Euclides proporciona un m´etodo eficiente para el c´alculo del gcd(a, b) sin necesidad de hallar factorizaciones, el s´ımbolo de Jacobi nos permite hacer lo mismo aunque no parezca evidente con la definici´on que hemos dado. Esta es una ventaja notable, ya que, como mencionamos en la introducci´on, no se conoce ning´un algoritmo eficiente para calcular factorizaciones de enteros. El contenido de esta secci´on se basa esencialmente en el tratamiento de [35]. Todo comienza con Gauss, quien denomin´o al siguiente resultado como el Teorema ´ Aureo. Se conoce hoy como la Ley de Reciprocidad Cuadr´atica de Gauss, uno de los resultados con m´as demostraciones distintas de la Historia de las Matem´aticas, contando actualmente con mas de 200. La demostraci´on original (por inducci´on) se encuentra en [13]. Pese a que no daremos la demostraci´on, veamos una breve explicaci´on: Teorema 3.14 (Ley de Reciprocidad de Gauss) Sean pyqprimos impares distintos. 1. −1 p= (−1)(p−1)/2=(1 si p≡1 (m´od 4) −1 si p≡3 (m´od 4) 3.2. C´ ALCULO EFECTIVO DEL S´ IMBOLO DE JACOBI 2. 2 p= (−1)(p2−1)/8=(1 si p≡1,7 (m´od 8) −1 si p≡3,5 (m´od 8) 3. q pp q= (−1)(p−1)(q−1)/4 Observaci´on 3.15 El apartado (1) es en realidad el Criterio de Euler (Teorema 3.8) aplicado a a=−1, junto con la observaci´on de que si p= 4s+r, entonces (−1)(p−1)/2= (−1)(r−1)/2, donde rs´olo puede ser 1 o 3. En el segundo, lo dif´ıcil es probar el primer caso (ver [32]). Por ´ultimo, notemos que el tercero puede reformularse as´ı: p q=         −q psi p≡1 (m´od 4) o si q≡1 (m´od 4) q psi p≡q≡3 (m´od 4). Observaci´on 3.16 Al igual que nos planteamos qu´e es lo que ocurre con los residuos cuadr´aticos, tambi´en podr´ıamos analizar lo mismo para los residuos de potencias mayores. De hecho, Gauss explor´o la posibilidad de extender su Ley de Reciprocidad Cuadr´atica a residuos de potencias mayores que 2. Sin embargo, se percat´o de que para abordar este problema era necesario considerar los n´umeros complejos y las ra´ıces de la unidad. Esta fue una de las razones por las cuales introdujo los enteros gaussianos Z[i]. No obstante, fue Eisenstein en 1844 el primero que proporcion´o una prueba completa de las correspondientes leyes de reciprocidad c´ubica y bicuadr´atica haciendo uso de extensiones de Z, de lo que podemos leer m´as en [3] . Ejemplo: Veamos c´omo usar estas propiedades para un c´alculo expl´ıcito del s´ımbolo de Legendre. En estas igualdades hemos marcado con Fel uso de la factorizaci´on en primos, con Rel uso de la Ley de Reciprocidad y con Del uso de la divisi´on eucl´ıdea. 26 31F =2 3113 31R = 1 ·31 13D =5 13R =13 5D =3 5R =5 3D =2 3R =−1 Observamos que en el primer caso se ha necesitado factorizar. Sin embargo, gracias al resultado de Jacobi que demostraremos a continuaci´on y que, en cierto sentido, generaliza la Ley de Reciprocidad Cuadr´atica de Gauss, podremos hacer este c´alculo, para nno necesariamente primo, sin necesidad de factorizar. Veamos la construcci´on. Sean nymdenotan enteros positivos impares, y aybenteros arbitrarios. Son inmediatas de comprobar las siguientes propiedades: 3.2. C´ ALCULO EFECTIVO DEL S´ IMBOLO DE JACOBI a n=b nsi a≡b(m´od n), equivale a Den el ejemplo anterior. 1 n= 1, 0 n= 0 a nb n=ab n Para las siguientes propiedades s´ı procede dar una demostraci´on: Teorema 3.17 (Ley de Reciprocidad de Jacobi) Sean aynenteros mayores que 3. Entonces, 1. −1 n= (−1)(n−1)/2=(1 si n≡1 (m´od 4) −1 si n≡3 (m´od 4) 2. 2 n= (−1)(n2−1)/8=(1 si n≡1,7 (m´od 4) −1 si n≡3,5 (m´od 4) 3. a nn a= (−1)(a−1)(n−1)/4=(1 si n≡1 (m´od 4) −1 si n≡3 (m´od 4) Antes de probar este resultado, presentamos dos lemas breves: Lema 3.18 La aplicaci´on γ:U4→ {±1}, n 7→ (−1)(n−1)/2 es un homomorfismo de grupos. Demostraci´on: Sean a, n ∈U4={1,3}(observemos que son impares). Hay que probar que γ(an) = γ(a)γ(n), es decir, que: (−1)(an−1)/2= (−1)(a−1)/2(−1)(n−1)/2 Esta ecuaci´on equivale a (−1)(an−1)/2−(a−1)/2−(n−1)/2= 1, lo que a su vez equivale a que an −1 2−a−1 2−n−1 2 sea par. Vemos f´acilmente que an −1 2−a−1 2−n−1 2=1 2(an −1−n+ 1 −a+ 1) = 1 2(n−1)(a−1). Como aynson impares, (n−1)(a−1) es divisible por 4, luego la ´ultima expresi´on es m´ultiplo de 2, y por tanto, par. □ 3.2. C´ ALCULO EFECTIVO DEL S´ IMBOLO DE JACOBI Lema 3.19 La aplicaci´on β:U8→ {±1}, n 7→ (−1)(n2−1)/8 es un homomorfismo de grupos. Demostraci´on: An´alogamente, sean a, n ∈U8={1,3,5,7}. De nuevo son impares y hay que probar que β(an) = β(a)β(n), es decir, que (−1)((an)2−1)/8= (−1)(a2−1)/8(−1)(n2−1)/8, lo que equivale a que (an)2−1 8−a2−1 8−n2−1 8 sea par. Vemos entonces, como en el caso anterior, que (an)2−1 8−a2−1 8−n2−1 8=1 8(an)2−1−a2+ 1 −n2+ 1=1 8(n2−1)(a2−1). Ahora bien, observemos que si n∈U8={1,3,5,7}, entonces n2≡1 (m´od 8), y lo mismo ocurre para a. Por tanto, como (n2−1) y (a2−1) son m´ultiplos de 8, se obtiene el resultado ya que la ´ultima expresi´on es m´ultiplo de 8 y por ende par. □ Ya estamos en condiciones de demostrar la Ley de Reciprocidad Cuadr´atica de Jacobi bas´andonos tanto en estos dos lemas como en la Ley de Reciprocidad Cuadr´atica de Gauss. Demostraci´on: Sean γyβlos morfismos de los lemas anteriores, y sean n= r Y i=1 pei i, a = s Y i=1 qfi i las factorizaciones en primos de nyarespectivamente. Para demostrar (1) notamos que γ(p) = −1 ppara todo primo impar ppor pura definici´on de γ. As´ı tenemos que −1 n= r Y i=1 −1 piei = r Y i=1 γ(pi)ei=γ r Y i=1 pei i!=γ(n) Probar (2) es similar, aprovechando la definici´on de βy su estructura de homomorfismo de grupos β(pi) = 2 pi, 2 n= r Y i=1 2 piei = r Y i=1 β(pi)ei=β r Y i=1 pei i!=β(n) El tercer punto es parecido, aunque hacemos uso de la Ley de Reciprocidad de Gauss 3.2. C´ ALCULO EFECTIVO DEL S´ IMBOLO DE JACOBI y de la tercera propiedad intruducida como inmediata: a nn a= r Y i=1 a piei · s Y j=1 n qjfj = r Y i=1   s Y j=1 qj pifj  ei · s Y j=1 r Y i=1 pi qjei!fj = r Y i=1 s Y j=1 qj pifjeipi qjeifj! = r Y i=1 s Y j=1 qj pi2 (−1)(pi−1)/2·(qj−1)/2!eifj Pero qj pi2= 1, luego tenemos: a nn a= s Y i=1 s Y j=1 (−1)eifj(pi−1)/2·(qj−1)/2 = r Y i=1   s Y j=1 (−1)fj(qj−1)/2  ei = r Y i=1 γ(a)ei(pi−1)/2 =(1 si γ(a) = 1 o si γ(n)=1 −1 si γ(a) = γ(n) = −1 =(1 si a≡1 (m´od 4) o si n≡1 (m´od 4) −1 si a≡n≡3 (m´od 4) □ Demos una idea general del procedimiento del c´alculo de manera efectiva sin la necesidad de factorizar como tal. En primer lugar, se reduce extrayendo factores 2 del siguiente modo : 2a n=a n si n≡ ±1 (m´od 8); en otro caso, 2a n=−a n=m n, atendiendo al segundo punto de la Ley de Reciprocidad (R2). Una vez hecho esto, si mynson ambos impares, entonces m n=n m=b m salvo que mynsean ambos congruentes con 3 m´odulo 4, en cuyo caso m n= −n m=b m, es decir, aplicar el tercer punto de la Ley de Reciprocidad (R3). Ahora toca calcular la divisi´on eucl´ıdea (D) y reducir bm´odulo m, quedando r m. 3.2. C´ ALCULO EFECTIVO DEL S´ IMBOLO DE JACOBI Volvemos al punto de partida y repetimos todos los pasos las veces que sea necesario hasta llegar a una situaci´on −1 poq p, con q < p primos (estar´ıamos en el caso del s´ımbolo de Legendre), acudiendo a la Ley de Reciprocidad de Gauss de nuevo para el c´alculo final y directo del resultado. Veamos c´omo calcular el s´ımbolo de Jacobi 1008 2307 utilizando las propiedades vistas. 1008 2307R2 =2 2307 2 2307 2 2307 2 2307 63 2307 R2 = (−1)463 2307=63 2307 R3 = (−1) 2307 63  D = (−1) 39 63 R3 = (−1)(−1) 63 39=63 39 R3 =24 39 R2 =2 392 392 393 39= 133 39 R3 = (−1) 39 3= 0. Por lo tanto, gracias a este c´alculo del s´ımbolo de Jacobi y la exponenciaci´on modular, ambos requiriendo O(log3(n)), el tiempo total para kiteraciones del Test de Solovay–Strassen es O(klog3(n)), como adelantamos en la secci´on previa. Aunque este test es simple y f´acil de implementar, lo que lo hace r´apido para n´umeros peque˜nos y medianos, no es eficiente para n´umeros muy grandes, ya que la complejidad del tiempo crece c´ubicamente con el tama˜no de entrada. A continuaci´on, se presenta un test cuya probabilidad de error es menor que la de Solovay-Strassen, por lo que en la actualidad este ´ultimo ha quedado superado. Cap´ıtulo 4 Test de Miller–Rabin Hist´oricamente, el Test de Solovay–Strassen fue el primer test probabil´ıstico de primalidad. Poco despu´es de que apareciera este test, fue eclipsado por el Test de Miller–Rabin, que es m´as f´acil de implementar (no se necesitan s´ımbolos de Jacobi) y m´as efectivo, ya que a pesar de ser un test probabil´ıstico, reduce la probabilidad de error m´as r´apidamente que Solovay–Strassen, como veremos al final del cap´ıtulo. Su origen se remonta a 1976. Las ideas originales de Gary Miller estaban ´ıntimamente relacionadas con uno de los problemas abiertos m´as rese˜nables en teor´ıa de n´umeros: la Hip´otesis Generalizada de Riemann (GRH), una generalizaci´on de la Conjetura 1.12 que debemos a Piltz, a finales del siglo XIX. En efecto, si esta fuera cierta, entonces el test determinista original tendr´ıa una complejidad de orden O(log4n) [23], relativamente eficiente en comparaci´on con muchos otros problemas computacionales. Aunque, como ya anticipamos en la secci´on de resultados generales, la Hip´otesis Generalizada de Riemann pese a que es considerado un problema de enorme importancia en la matem´atica contempor´anea, sigue abierto a d´ıa de hoy, luego no resulta definitivo tener un test efectivo si para su implementaci´on hacemos uso de ´el. Fue Michael Rabin, sobre el a˜no 1980 [30], quien modific´o el test eliminando la dependencia de la GRH. No obstante, esta nueva versi´on hizo al algortimo perder eficiencia computacional y es la que recibe hoy en d´ıa el nombre de Test de Miller– Rabin. Presentamos a continuaci´on este test probabil´ıstico de tipo Montecarlo. Observaci´on 4.1 Recordemos, como ya ha aparecido alguna vez en esta memoria, que si pes un primo y aun entero tal que a2≡1 (m´od p), entonces a≡1 (m´od p) o bien a≡ −1 (m´od p). Esto es directo, ya que dado un primo p, en el cuerpo Fp, las ´unicas ra´ıces de 1 31 (es decir, las ra´ıces del polinomio x2−1) son 1 y −1. Lema 4.2 Sea un primo n > 2 y sea a∈Un. Escribamos n= 2sd+ 1 con dimpar. Entonces se verifica una de las dos condiciones siguientes, 1. ad≡1 (m´od n). 2. a2rd≡ −1 (m´od n), para alg´un 0 ≤r < s. Demostraci´on: Consideremos la sucesi´on a2sd, a2s−1d, . . . , a2d, ad; donde observemos que cada t´ermino de la sucesi´on es el cuadrado del posterior. Por el teorema de Fermat, a2sd=an−1≡1 (m´od n), luego (a2s−1d)2≡1 (m´od n) y por lo tanto a2s−1des una ra´ız cuadrada de 1 m´odulo n. Por la observaci´on anterior, obtenemos que a2s−1d≡ ±1 (m´od n) Si a2s−1d≡ −1 (m´od n), obtenemos el resultado. En caso contrario, a2s−1d≡1 (m´od n), luego (a2s−2d)2≡1 (m´od n) y por lo tanto a2s−2des una ra´ız cuadrada de 1 m´odulo ny en consecuencia a2s−2d≡ ±1 (m´od n). Iterando el razonamiento anterior, concluimos que alguno de los t´erminos de la sucesi´on a2rd≡ −1 (m´od n), o bien todos los t´erminos son congruentes a 1, en particular ad≡1 (m´od n). □ Nos encontramos en la misma situaci´on que en el cap´ıtulo previo, acabamos de introducir una nueva propiedad que cumplen los n´umeros primos. Sin embargo, nos vuelve a atacar la duda de si esta condici´on es es suficiente o necesaria. ¿Todo nimpar que cumpla la propiedad del Lema 4.2 es primo? Definici´on 4.3 Sea un nun entero impar de la forma n= 2sd+ 1, con dimpar. Se dice que nes un pseudoprimo (fuerte) respecto de la base a∈Unsi cumple alguna de las condiciones del Lema 4.2. La siguiente proposici´on pone de manifiesto que ser pseudoprimo fuerte es m´as exigente que ser pseudoprimo de Euler y, por tanto en particular no existe el an´alogo a los n´umeros de Carmichael para la propiedad ser pseudoprimo fuerte. Recuperando de nuevo el ejemplo n= 2821, observamos que este es el menor n´umero de Carmichael que no es ni pseudoprimo de Euler ni fuerte en base 2. Proposici´on 4.4 Sea nun pseudoprimo fuerte respecto de la base a, entonces nes pseudoprimo de Euler respecto de la base a. Demostraci´on: Sea n−1 = 2sdcon dimpar y supongamos que nes pseudoprimo fuerte en la base a. Tenemos que distinguir dos casos, en paralelo a la propia definici´on de pseudoprimalidad fuerte. Caso 1: Si ad≡1 (m´od n), entonces a(n−1)/2=a2s−1d≡1 (m´od n), y como des impar conserva el signo como exponente, entonces a n=a nd=ad n=1 n= 1. Caso 2: Supongamos que a2rd≡ −1 (m´od n) con 0 ≤r < s. Sea pun divisor primo de ny pongamos p−1 = 2tc, con cimpar. Entonces a2rdc ≡ −1 (m´od n) y, por tanto, a2rdc ≡ −1 (m´od p) (4.1) Por el Peque˜no Teorema de Fermat tambi´en tenemos que a2tdc =a2tcd≡1 (m´od p) (4.2) De (4.1) y (4.2) se deduce que t>r. As´ı, utilizando el Criterio de Euler (Teorema 3.8) para ptenemos a p=a pd =a(p−1)/2d=a2t−1dc =a2rdc2t−(r+1) = (−1)2t−(r+1) (m´od p), es decir , a p=(1 si t>r+ 1; −1 si t=r+ 1.(4.3) Ahora bien, si npasa la prueba para todas nuestras elecciones aleatorias de a (supongamos que intentamos kbases diferentes a) entonces sabemos por el Teorema 4.7 que la probabilidad de que nsea compuesto, Pnpasa el test≤1 4k , Obs´ervese que esto es mejor que en el caso de la prueba de Solovay–Strassen, donde la estimaci´on an´aloga es una probabilidad de 1/2k. El c´alculo de nuestros ejemplos el cual encontramos en el ap´endice, resulta: 12432902008176640000 compuesto , es divisible por 2 23044260448006092643 compuesto , paro en la iteracion 0 con la base 1446122688032912871 31816787885244115403 probablemente primo , pasa el test despues de 19 iteraciones 4True A pesar de la baja probabilidad de error que podemos obtener al iterar tantas veces como queramos, sigue habiendo una carencia a la hora de usar este test, una carencia de independencia. Supongamos que a1ya2se eligen de antemano. Si nes un pseudoprimo en base a1, entonces es m´as probable que sea pseudoprimo en base a2que un n´umero que no lo era en base a1. Por ejemplo, un pseudoprimo en base 2 es pseudoprimo para muchas m´as bases que el n´umero compuesto impar promedio del mismo tama˜no no pseudoprimo en base 2. De hecho, de los 21853 pseudoprimos en base 2 menores que 25 ·109, 4709 de ellos tambi´en son pseudoprimos en base 3; 2522 de ellos son pseudoprimos en base 2, en base 3 y en base 5 simult´aneamente; y 1770 de ellos son pseudoprimos en base 2, en base 3, en base 5 y en base 7 simult´aneamente [27]. Si los hechos ser pseudoprimo en base a1y ser pseudoprimo en base a2fueran independientes, esperar´ıamos que ninguno de los primeros 21853 pseudoprimos en base 2 fuera pseudoprimo en base 3, 5 ´o 7. ¿Podr´ıamos eliminar esta dependencia de alg´un modo? Para discutir esta afirmaci´on, damos paso a una nueva definici´on de pseudoprimos y al ´ultimo test que nos concierne. Cap´ıtulo 5 Test de Baillie-PSW 5.1. Pseudoprimos de Lucas Para introducir el ´ultimo tipo de pseudoprimos hemos de definir en primera instancia una familia de sucesiones, que son la base de nuestro nuevo concepto. Definici´on 5.1 ([2]) Sean D,PyQenteros tal que D=P2−4Q= 0, y P > 0. Sea U0= 0, U1= 1, V0= 2 y V1=P. Definimos recursivamente las sucesiones de Lucas {Uk}y{Vk}con par´ametros {D, P, Q}como Uk=PUk−1−QUk−2, Vk=P Vk−1−QVk−2. Como podemos observar, estas dos sucesiones tienen la misma recurrencia, su ´unica diferencia son las condiciones iniciales. Podemos ver un an´alisis profundo de estas sucesiones en [4, Sec. 4]. Veamos a continuaci´on una propiedad que cumplen sin dar su demostraci´on, pues recae en propiedades gen´ericas de sucesiones. Propiedad 5.2 ([2]) Sean αyβdos ra´ıces del polinomio x2−Px +Q. Tomando k≥0, tenemos que Uk=αk−βk α−β, Vk=αk+βk. Definici´on 5.3 En las condiciones anteriores, para todo nentero impar, definimos δ(n) = n−ϵ(n), siendo ϵ(n) = D nel s´ımbolo de Jacobi introducido en el cap´ıtulo 3. Observaci´on 5.4 La funci´on δ(n) ´unicamente toma los valores {n−1, n, n + 1}. 41 5.1. PSEUDOPRIMOS DE LUCAS Teorema 5.5 Sea pun primo impar tal que gcd(Q, p) = 1, entonces Uδ(p)≡0 (m´od p). Demostraci´on: La siguiente demostraci´on est´a basada en de [25]. Igual que antes, llamamos αyβa las ra´ıces de x2−Px +Q. Pongamos α=P+√D 2, β =P−√D 2. Tenemos entonces Un=αn−βn √D,con αn= P+√D 2!n , βn= P−√D 2!n . Despejamos P+√Dn−P−√Dny aplicamos la expresi´on del binomio: Un√D2n=P+√Dn−P−√Dn = n X k=0 n kPn−k√Dk− n X k=0 n kPn−k−√Dk = n X k=0 n kPn−kDk/2−(−1)kDk/2 = 2 n X k=1 kimpar n kPn−kDk/2. De esta manera, tenemos Un=1 2n−1 n X k=1 kimpar n kPn−kD(k−1)/2. Ahora veamos qu´e valores puede tomar δ(p) con psea primo, y hallemos Uδ(p)m´od p. Caso 1: δ(p) = p. Entonces, D p≡0 m´od p. Notando que p k≡0,para 1 ≤k≤p−1, vemos que solo sobrevive el ´ultimo sumando: Uδ(p)=Up= 21−pp pP0D(p−1)/2= 21−pD(p−1)/2≡21−pD p≡0 m´od p, donde hemos utilizado el Criterio de Euler 3.1 para obtener finalmente Uδ(p)≡0 m´od p. 5.1. PSEUDOPRIMOS DE LUCAS Caso 2: δp=p+ 1. Entonces, D p≡ −1 m´od p. De nuevo p+1 k≡0 m´od ppara 2≤k≤p−1, as´ı: Uδ(p)=Up+1 = 21−(p+1) p X k=1 kimpar p+ 1 kPp+1−kD(k−1)/2 ≡2−p(p+ 1)Pp+ (p+ 1)PD(p−1)/2 ≡2−p(p+ 1)P(Pp−1+D(p−1)/2) ≡2−1P1 + D p≡0 m´od p, donde, aparte del Criterio de Euler, hemos usado el Peque˜no Teorema de Fermat con P(p−1) ≡1 m´od p. Caso 3: δp=p−1, es decir D p≡1 m´od p. Ahora por definici´on, Up+1 =PUp−QUp−1 As´ı que, QUp−1=PUp−Up+1 ≡PD p−2−1P1 + D p≡P−2−1P·2≡0 m´od p. Ahora, como pno divide a Q,Uδ(p)=Up−1≡0 m´od p.□ Podemos observar que esta propiedad que cumplen los primos es an´aloga al Peque˜no Teorema de Fermat para las sucesiones de Lucas, por lo que nos lleva a la misma pregunta que nos hemos estado haciendo hasta ahora en cada cap´ıtulo: ¿Aparecen n´umeros compuestos cumpliendo esta propiedad o por el contrario es cierto el rec´ıproco del Teorema 5.5? Definici´on 5.6 Un n´umero compuesto nse dice pseudoprimo de Lucas con par´ametros PyQsi Uδ(n)≡0 m´od n. En efecto, seguimos sin tener una condici´on suficiente de primalidad, un ejemplo de pseudoprimalidad de Lucas es 14209 = 13·1093 con los par´ametros P= 1, Q =−3. 5.2.5 Podemos encontrar diversos resultados sobre la densidad de los pseudoprimos de Lucas que ponen en manifiesto su rango de aparici´on en las series de Lucas en [25], donde adem´as encontramos una cota an´aloga a la que dimos para los n´umeros de Carmichael que controla la frecuencia de estos. 5.1. PSEUDOPRIMOS DE LUCAS Teorema 5.7 Dados PyQ, denotamos por Lc(x) el n´umero de pseudoprimos de Lucas con par´ametros PyQmenores que x. Existe una constante ctal que para un xlo suficientemente grande: Lc(x)< x exp −cplog xlog log x No obstante, nuestro objetivo no es tanto analizar con profundidad estos tipos de pseudoprimos, si ponerlos en relaci´on con los otros tipos de pseudoprimos que hemos presentado previamente. Un primer resultado que nos encamina al test que queremos presentar y que pretende dar soluci´on al tema de la dependencia que introdujimos al final del cap´ıtulo anterior fue dado por Baillie y Wagstaff en [2]. En este trabajo, declaran haber probado 50 n´umeros de Carmichael peque˜nos con un test de primalidad de Lucas y todos ellos fueron determinados correctamente como compuestos. Es m´as, prueban que los 21853 pseudoprimos en base 2 que hay por debajo del umbral 25·109tambi´en fallaron para tests de primalidad de Lucas siguiendo las elecciones de par´ametros A y B que ahora introduciremos. Efectivamente es razonable pensar que no hay solapamientos (o hay muy pocos) entre los dos tipos de n´umeros y que una manera muy efectiva de probar la primalidad ser´ıa combinar un test de Miller con un test de Lucas. No obstante, para determinar si un n´umero es pseudoprimo de Lucas, debemos fijar antes PyQ. ¿Hay preferencias para la elecci´on de estos par´ametros? En primer lugar, no escogeremos un Dque sea un residuo cuadr´atico m´odulo n1. La raz´on es sencilla: si D=b2, es decir, D n= 1, y P=b+ 2, entonces Q=b+ 1 y α=P+√D 2≡P+b 2=b+ 1 = Qm´od n, β =P−√D 2≡P−b 2= 1 m´od n y, por tanto Uδ(n)=Un−1≡Qn−1−1 Q−1. Por lo que Qn−1≡1 m´od n, es decir, estar´ıamos realizando una mera prueba de primalidad como la de Solovay-Strassen. Una buena manera de prevenir esto es fijar D n=−1. Obviamente, si en la b´usqueda de un Dcumpliendo esto topamos con D n= 0 habr´ıamos hallado un factor de n(un testigo de primalidad). Aunque haya muchos m´etodos de hacer la elecci´on [2], los dos m´as conocidos son: M´etodo A (propuesto por John Selfridge): Sea Del primer elemento de la sucesi´on 5,−7,9,−11,13, . . . para el cual D n=−1. Sea P= 1 y Q= (1 −D)/4. 1Si en el segundo paso no se exige que el s´ımbolo de Jacobi D n=−1, entonces un s´uper n´umero de Carmichael pasa el test, una nueva definici´on de pseudoprimo que dejamos como inter´es del lector. 5.1. PSEUDOPRIMOS DE LUCAS M´etodo B (preferido por Baillie): Sea Del primer elemento de la sucesi´on 5,9,13, . . . tal que D n=−1. Sea Pel menor entero impar que sea mayor a D1/2y Q= (P2−D)/4. Observaci´on 5.8 [25] En el M´etodo A no interesa D=−3, ya que en ese caso P=Q= 1, lo cual genera una sucesi´on de Lucas peri´odica y, para esta, todos los n impares que no sean m´ultiplos de 3 son pseudoprimos de Lucas con par´ametros 1, 1. Observaci´on 5.9 Con el M´etodo A los primeros pseudoprimos de Lucas que encontramos son: 323, 377, 1159, 1829 y 3827; mientras que con el M´etodo B hallamos: 323, 377, 1349, 2033 y 2651. Se deja al lector curiosear sobre la lista de estos pseudoprimos y de todos los vistos hasta ahora en OEIS 2. Realmente no es cierto que ning´un pseudoprimo de Fermat es pseudoprimo de Lucas, de hecho 341 es pseudoprimo respecto a la base 2 y pseudoprimo de Lucas (7,2). Lo que Baillie y Wagstaff defienden en [25] es que dado un pseudoprimo en base a, si buscamos sucesiones de Lucas para las cuales D n=−1, acabar´aemos encontr´andolas, seguramente. Sin embargo, la mayor´ıa de pseudoprimos de Lucas con D n=−1 son pseudoprimos de Fermat para muy pocas bases a. Esta es la raz´on por la que combinando los pseudoprimos fuertes (que superan el problema de los n´umeros de Carmichael) y los pseudoprimos de Lucas haciendo buena elecci´on de los par´ametros, obtenemos una muy buena evidencia de primalidad. Aqu´ı nace el test que da nombre a este cap´ıtulo, concebido por primera vez por Baillie (1980) con mejoras a˜nadidas por Pomerance, Selfridge y Wagstaff, que no es otra cosa que una combinaci´on del test de Miller–Rabin y el de Lucas. Un pseudoprimo que pase el test recibe el nombre de BPSW. Carl Pomerance (1984) conjetur´o en [29] que hay infinitos pseudoprimos BPSW, argumentando tambi´en que para xlo suficientemente grande, el n´umero de pseudoprimos BPSW menores que xsupera x1−µ, donde µes un n´umero positivo arbitrariamente peque˜no predefinido. No obstante, por el momento no se han encontrado ejemplos de tales pseudoprimos, por lo que en caso de no existir, implicar´ıa la existencia de un test de primalidad 2OEIS(Online Encyclopedia of Integer Sequences). Es una base de datos en l´ınea que contiene informaci´on sobre una variedad de sucesiones num´ericas, incluidos los n´umeros de Carmichael, pseudoprimos de Euler, fuertes y de Lucas, entre numerosas cosas m´as. Una vez que encuentres la sucesi´on que est´as buscando, puedes explorar sus propiedades, f´ormulas matem´aticas asociadas, referencias bibliogr´aficas y otros detalles que est´en disponibles http://oeis.org/A005845 5.1. PSEUDOPRIMOS DE LUCAS determinista en tiempo polinomial . Es m´as, el 13 de junio de 2009, Jeff Gilchrist [15] confirm´o que no hay pseudoprimos BPSW menores que 1017 y es interesante consultar esta referencia, donde podemos observar su trabajo expl´ıcitamente. Tambi´en se demuestra en [24] que no exixte ning´un pseudoprimo BPSW por debajo de 264 (264 ≈1845 ·1019). Introduzcamos por fin el algoritmo de una variante del test dada por Pomerance en 1984: Algorithm 4 Algoritmo BPSW Entrada: (n, M)∈N≥3×N, con nimpar y Muna cota superior para divisores sencillos Salida: n compuesto on probablemente primo 1: Comprobar si ntiene divisores menores que M. 2: Realice a nuna prueba de Miller–Rabin en base 2. 1. Si nno es un pseudoprimo fuerte con base 2, detenerse; n compuesto. 2. Si lo es, continuar con el paso siguiente. 3: Realice a nuna prueba de Lucas mediante las elecciones del M´etodo A o B. 1. Si nno es un pseudoprimo de Lucas, detenerse; n compuesto. 2. Si lo es, n probablemente primo. Observaci´on 5.10 El primer paso es s´olo por eficacia ya que en caso de que tenga un divisor primo peque˜no no tendr´ıa sentido continuar con el algortimo. En el segundo paso se elige la base 2 pues se conocen muchos resultados sobre los pseudoprimos fuertes en base 2 que los distinguen de los pseudoprimos de Lucas, y por tanto, su combinaci´on hace buen trabajo en distinguir los n´umeros primos de los compuestos. No obstante, otras bases podr´ıan funcionar igual de bien. Observaci´on 5.11 No hay mejora en cuanto al orden de complejidad respecto a los algoritmos ya vistos pues es una combinaci´on de ambos, y tanto el test de Miller– Rabin como el de Lucas tienen complejidad O(log3n). Aplicando el alortimo a nuestros ejemplos implementado en el Ap´endice 5.2.4 obtenemos: 1is_probable_bpsw_prime (n1 ,20) 2OUT: ’compuesto , tiene como factor ’, 2 3is_probable_bpsw_prime (n2 ,20) 4OUT: ’compuesto , falla test de Miller en base 2’ 5is_probable_bpsw_prime (n3 ,20) 5.2. EJEMPLO DE APLICACI´ ON CON SAGEMATH 6OUT: 1375749999709520848 1001324354255196490 7’compuesto , falla test de Lucas para los parametros anteriores ’ 5.2. Ejemplo de aplicaci´on con SageMath Muchos sistemas de ´algebra computacional y paquetes de software utilizan alguna versi´on de la prueba de primalidad de Baillie-PSW. Algunos ejemplos son la funci´on isprime de Maple, la funci´on PrimeQ de Mathematica, las funciones isprime y ispseudoprime de PARI/GP, entre muchos otros. Un en particular y de nuestro inter´es es la funci´on en SageMath is pseudoprime de SageMath documentation, que usa una versi´on de la prueba de primalidad de Baillie-PSW combinando una prueba de primos probables fuertes de Fermat y una prueba de Lucas. Como hemos visto previamente, este test resulta infalible para n´umeros menores que 264 [24], por lo que se convierte en un algortimo determinista al trabajar con n´umeros menores que esta magnitud. Esto nos ha permitido calcular el dato π(2,5×1010) de la tabla comparativa entre n´umeros de Carmichael y primos menores que x. Debido a que ya ten´ıamos el dato π(1010), hemos intentado ahorrar memoria calculando ´unicamente los primos entre los umbrales. El procedimiento ha sido el siguiente: 1def contar_primos (n , x): 2contador = 0 3for iin range (n + 1, x): 4if is_pseudoprime (i): 5contador += 1 6return contador 7 8contar_primos (10^(10) , int (2.5*10^(16))) 9OUT: 10 636934894 Por lo tanto, gracias al dato π(1010) de la tabla 2.2, obtenemos con total fiabilidad π(2,5·1010) = 636934894 + 455052511 = 1099985405. Es interesante comparar este resultado con la misma prueba usando ´unicamente Miller-Rabin con k= 5 bases, cuyo c´alculo encontrar´eis en la secci´on del Ap´endice 5.2.6. El c´alculo realizado con SageMath, que llev´o m´as de 30 horas, dio el mismo resultado que usando el test Baillie-PSW. Con esto concluimos que efectivamente no hay pseudoprimos fuertes que sean a su vez pseudoprimos de Lucas para n´umeros menores que el umbral π(2,5·1010). Ap´endice: Implementaci´on en SageMath Presentamos en este ap´endice la implementaci´on con ejemplos en SageMath de los algoritmos expuestos en el trabajo; en particular, el de Solovay-Strassen, MillerRabin y Baillie-PSW. Adem´as, se comprueba la pseudoprimalidad de un pseudoprimo de Lucas y se presenta el c´alculo de π(x) con xentre 1010 y 2,5×1010 utilizando Miller-Rabin. 5.2.1. Elecci´on de nicon SageMath 1# N\’ umero de 19 cifras con factores primos peque \~ nos 2n1 = factorial (20) 3 4# C\’ alculo de dos primos grandes cuyo producto resulte en un n\’ umero de 19 5cifras 6k = 9 7a = ZZ . random_element (10^( k -1) , 10^ k). next_prime () 8b = ZZ . rand om_ ele men t (10^(( k +1) -1) , 10^( k +1) ). next_prime () 9n2 = a * b 10 # Calculo de un primo de 19 cifras 11 l = 19 12 n3 = ZZ. random_element (10^(l -1) , 10^ l). next_prime () 13 # Mostrar los resultados 14 print ("n1 :", 2432902008176640000) 15 print ("n2 :", 3840536061136845209) 16 print ("n3 :", 1816787885244115403) 5.2.2. Primalidad de nicon Solovay-Strassen Implementamos el algoritmo de Solovay-Strassen, para ello se usan las funciones implementadas en SageMath: jacobi symbol, importada de sage.arith.misc, 48 5.2. EJEMPLO DE APLICACI´ ON CON SAGEMATH ypower mod, las cuales hacen un c´alculo efectivo del S´ımbolo de Jacobi y la exponenciaci´on modular respectivamente, con una peque˜na modificaci´on de la funci´on jacobi symbol como sigue: 1from sage . arith . misc import jacobi_symbol 2def jacobi (a ,n ): 3if jacobi_symbol (a, n)== -1: 4return n -1 5else: 6return jacobi_symbol (a , n) As´ı queda: 1import random 2def SolovayStrassen (n , k): 3for iin range (1, k+1): 4a = random . randint (2 , n -1) 5if gcd (a,n) !=1: 6print (n , "es compuesto y falla el test en la iteracion ", i , "con la base ", a) 7return False 8if jacobi (a , n) != power_mod (a , (n -1) //2 , n): 9print (n , "es compuesto y falla el test en la iteracion ", i , "con la base ", a) 10 return False 11 12 print (n , "es probablemente primo y pasa el test tras 20 iteraciones " ) 13 return True 14 15 SolovayStrassen (n1 , 20) 16 SolovayStrassen (n2 , 20) 17 SolovayStrassen (n3 , 20) 18 19 OUT: 20 2432902008176640000 es compuesto y falla el test en la iteracion 1 con la base 1868969210451108746 21 3044260448006092643 es compuesto y falla el test en la iteracion 1 con la base 2680792065180999020 22 1816787885244115403 es probablemente primo y pasa el test tras 20 iteraciones 5.2.3. Primalidad de nicon Miller-Rabin 1import random 2def miller_rabin(n, k=20): 3if n <= 1: 4return False BIBLIOGRAF´ IA [28] C. Pomerance: On the distribution of pseudoprimes. Math. Comp. 37 (1981) 587–593. [29] C. Pomerance: Are there counter-examples to the Baillie-PSW primality test? Preprint (1984) https://web.archive.org/web/20191121062007/http: //www.pseudoprime.com/dopo.pdf [30] M. O. Rabin Probabilistic Algorithm for Testing Primality. Journal of Number Theory 12 (1980) 128–138. [31] R. Rivest, A. Shamir, L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21 (2) 120–126. [32] K.H. Rosen: Elementary number theory and its applications, 5th Edition. Pearson/Addison-Wesley (2005). [33] B. Rosser: The n-th prime is greater than nlog(n).Proceedings of the London Mathematical Society 2(1939) 21–44. [34] R.M. Solovay, V. Strassen: A fast Monte-Carlo test for primality. SIAM Journal on Computing 6(1977) 84–85. [35] J.L. Varona: Recorridos por la Teor´ıa de N´umeros, 2a Edici´on. Electrolibris (2019).