Departamento de matemáticas

Números primos

Un número primo es un número entero mayor que cero, que tiene exactamente dos divisores positivos. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Conviene observar que con cualquiera de las dos definiciones el 1 queda excluido del conjunto de los números primos.

Ejemplos:

7. a) El 7 es primo. Sus únicos divisores son 1 y 7. Sólo puede expresarse como producto de 71.
   b) El 15 no es primo. Sus divisores son 1, 3, 5 y 15. Puede expresarse como 3·5. (y también como 15·1)

El término primo no significa que sean parientes de alguien. Deriva del latín «primus» que significa primero (protos en griego). El teorema fundamental de la aritmética afirma que todo número entero se expresa de forma única como producto de números primos. Por eso se les considera los «primeros», porque a partir de ellos obtenemos todos los demás números enteros. (El 15 se obtiene multiplicando los primos 3 y 5)

Los 25 primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97, que son todos los primos menores que 100.

En la siguiente tabla tenemos todos los primos menores que 1000, que hacen un total de 168 (21×8)

Póster con los números primos hasta 1000 (pdf)     Listado con los primos menores que 1.000.000 (txt) 

Para ver los 10.000 primeros números primos pincha aquí

Primos en el anillo de los enteros de Gauss

Cómo averiguar si un número es primo.

    El algoritmo más sencillo que puede utilizarse para saber si un número n es primo es el de la división. Se trata de ir probando para ver si tiene algún divisor propio. Para ello vamos dividiendo el número n entre 2, 3, 4, 5, … , n-1. Si alguna de las divisiones es exacta (da resto cero) podemos asegurar que el número n es compuesto. Si ninguna de estas divisiones es exacta, el número n es primo. Este método puede hacerse más eficiente observando simplemente, que si un número es compuesto alguno de sus factores (sin contar el 1) debe ser menor o igual que √ n. Por lo tanto, el número de divisiones a realizar es mucho menor. Sólo hay que dividir entre 2, 3, 4, 5, … , [√ n]. En realidad, bastaría hacer las divisiones entre los números primos menores o iguales que √ n.

     Ejemplo: Para probar que 227 es primo sabiendo que √227 = 15’0665… basta con ver que no es divisible entre 2, 3, 5, 7, 11 y 13.

     Este procedimiento resulta eficiente para números pequeños o que tienen factores pequeños. Sin embargo si el número tiene por ejemplo unas 20 cifras y es primo, habrá que realizar miles de millones de divisiones para comprobarlo.  Aunque un ordenador pueda realizar millones de divisiones en un segundo, el tiempo necesario es bastante considerable. Y cuando el número de dígitos aumenta el tiempo necesario ¡¡crece de forma exponencial!!

    Ejemplo práctico: Supongamos que queremos saber si un número de unas 50 cifras es primo. La raíz cuadrada de un número de este orden está en torno a 1025. Si un ordenador hace 1000 millones de divisiones por segundo, necesitará 1025/109 segundos; es decir, 1016 segundos. Este tiempo equivale, aproximadamente, a 1’6*1014 minutos, que son 2’7*1012 horas, o también 1’16*1011 días, aproximadamente  3’17*108 años. Que para hacer esto se necesiten 317.097.920 años se me antoja una tarea poco recomendable. Y si nos decidiésemos a llevarla a cabo, ¿sería útil esta información pasado todo este tiempo?  O más drástico todavía, ¿seguiría existiendo nuestra especie entonces?

    Debemos pues, buscar una alternativa que nos permita responder a este problema de una forma más favorable; necesitamos un algoritmo más eficiente.

    Una respuesta puede ser el teorema pequeño de Fermat. Este teorema afirma que si n es primo y mcd(a,n) = 1, entonces an-1 ≡ 1 (mod n). Hay que tener en cuenta que la exponenciación modular puede realizarse en un tiempo bastante favorable, si se hace de forma adecuada (hay algoritmos que nos dan la respuesta en tiempo polinómico)

    Ejemplo: Queremos comprobar si el número 15 es primo o no (utilizando esta propiedad). Tomamos a = 2, n = 15, y evaluamos 214 (mod 15). La respuesta es 214 ≡ 4 (mod 15). Podemos asegurar entonces que 15 es compuesto. Probemos con a = 2, n = 341, evaluamos 2340 (mod 341) y obtenemos que 2340 ≡ 1 (mod 341). Esto no nos permite deducir que 341 sea compuesto, pero tampoco que sea primo. Al probar con a=3 tenemos 3340 ≡ 56 (mod 341), lo cual implica que 341 es compuesto. 

    A los números que se comportan como el 341 en el ejemplo anterior se les llama pseudoprimos para la base 2 (se comportan como un primo para a=2). Este comportamiento es bastante más peculiar peculiar para algunos números. Tomando por ejemplo a=2 y n=561, obtenemos que 2560 ≡ 1 (mod 561), 3560 ≡ 1 (mod 561), 5560 ≡ 1 (mod 561)  y así con todas las bases con las que probemos. Es decir, se comporta como un primo para cualquier base que elijamos. Sin embargo, 561 es compuesto (561 = 3·11·17). A los números que como éste, son pseudoprimos para todas las bases se les llama números de Carmichael. Los números de Carmichael menores que 100.000 son 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973 y 75361. 

Desde luego, no parecen muy abundantes. Los expertos se preguntaban en los años 80 si serían un conjunto finito, con lo cual una vez identificados se podrían «evitar» fácilmente, aunque la creencia generalizada apuntaba a que el conjunto era infinito. Se demostró que si un número es de Carmichael debe ser libre de cuadrados y producto de al menos tres primos distintos. En 1994, Alford, Granville y Pomerance demostraron que existen infinitos números de Carmichael. De hecho, su resultado indica que para n suficientemente grande C(n) > n2/7, donde C(n) es la cantidad de números de Carmichael menores que n.

    Para evitar este contratiempo, podemos recurrir a un teorema un poco más fino debido a Euler. Este resultado afirma que si n es primo y mcd (a,n)=1, entonces a(n-1)/2 ≡ ±1 (mod n). Con esto evitamos que algunos números compuestos puedan pasar por primos como ocurre utilizando el teorema pequeño de Fermat.

    Ejemplo: Para comprobar que 91 es compuesto basta ver 245 ≡ 57 (mod 91). ¿Y que pasa con un número de Carmichael como el 561?. Veamos 2280 ≡ 1(mod 561), pero 5280 ≡ 67 (mod 561). Parece que esto funciona.

    Pero todavía podemos afinar un poco más. La idea es que si n es primo, entonces Zn es un cuerpo. Y en un cuerpo las únicas raíces cuadradas de 1 son 1 y -1. En el último ejemplo estamos diciendo que Z561 no es un cuerpo porque en él, la raíz de 1 es 67, y por tanto 561 no es primo. Si tomamos n-1 y lo dividimos entre 2 de forma sucesiva, mientras sea posible, estamos extrayendo raíces cuadradas y se trata de comprobar si los resultados dan siempre 1 ó -1. Esto da lugar al test de Miller-Rabin.

    Ejemplo: Tomando n = 561 hacemos 2280 (mod 561) ≡ 1 ,  2140 (mod 561) ≡ 67, que continuaría con 270 y  235, pero ya no es necesario calcularlos porque tenemos que la raíz cuadrada de 1 es 67 (mod 561). Por tanto, 561 es compuesto.

    Si al llegar a 235 no obtenemos un resultado distinto de +1 ó -1, tendríamos que elegir otra base. Y ahí es donde podemos tener dificultades, porque si n es bastante grande quizá tengamos que probar con muchas bases y la respuesta tardará en llegar. Y podemos empezar a preguntarnos si la tardanza se debe a que n es primo o porque es un compuesto que se comporta como un primo para un conjunto «grande» de bases. ¿Qué debemos hacer entonces? La solución es determinar el número de bases con las que tenemos que probar para asegurar que un número compuesto no pase la prueba como si fuese primo.

Definiciones: Si un entero n compuesto e impar verifica la congruencia de Euler para la base b, entonces n es un pseudoprimo de Euler para la base b. Asímismo, si n pasa el test de Miller-Rabin para la base b, entonces n es un pseudoprimo fuerte para la base b. Los siguientes resultados nos dan la respuesta a la cuestión del párrafo anterior.

Proposición: Si n es compuesto e impar, al menos la mitad de las bases b que verifican 0<b<n, no satisfacen la congruencia de Euler.

Teorema (Rabin): Si n es un entero compuesto impar, entonces n es un pseudoprimo fuerte para la base b, para a lo sumo un 25% de las posibles bases que verifican 0 < b < n, mcd(b,n) = 1.

    Desde luego que el teorema anterior no es para tirar cohetes. Probar con un 25% de las bases es algo descomunal si n es un número grande. Sin embargo, también hay que decir, que experimentalmente se ha comprobado que el test es mucho más eficiente de lo que indica la acotación del 25%. Es decir, cuando el número es compuesto, basta probar con unas pocas bases (la mayoría de veces con una sola) para demostrar que el número es compuesto. Si probamos con varias bases y nuestro número pasa el test, la probabilidad de que sea primo es muy pequeña. Y se puede elegir el número de bases que queramos de manera que la probabilidad sea menor que una cota prefijada de antemano.

Yendo un poco más lejos, hay un resultado de Miller basado en la hipótesis generalizada de Riemann, que afirma lo siguiente:

Teorema (Miller, 1976): Si la hipótesis generalizada de Riemann es cierta y n es un entero compuesto impar, entonces n no pasa el test de Miller-Rabin para alguna base b < 2·log2n  (¿¿teorema de bach, aukemy, montgomery 1985??)

    Este resultado implicaría un test de primalidad en tiempo polinómico del orden de O(log5n).

    En la tabla de abajo podemos ver la cantidad de números de Carmichael y pseudoprimos para la base 2. Por ejemplo, el primer 1 de la fila que comienza con 103 indica que sólo hay un número de Carmichael menor que 1000, y el 3 que sigue que hay 3 pseudoprimos para la base 2 menores que 1000. 

( Nota: Los pseudoprimos de Euler también son llamados a veces pseudoprimos de Euler-Jacobi )

Tabla 2: Pseudoprimos y números de Carmichael

    Los primeros pseudoprimos para la base 2 son 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, …
    Los primeros pseudoprimos para la base 3 son 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2821,…
    Los primeros pseudoprimos para la base 5 son 4, 124, 217, 561, 781, 1541, 1729, 1891, …

    Los primeros pseudoprimos de Euler para la base 2 son 561, 1105, 1729, 1905, 2047, 2465, …
    Los primeros pseudoprimos de Euler para la base 3 son 121, 703, 1729, 1891, 2821, 3281, 7381, …

    Los primeros pseudoprimos fuertes para la base 2 son 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, …

    Los primeros pseudoprimos fuertes para la base 3 son 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, …

    Estos ejemplos nos permiten ver que si en lugar de la base 2 utilizamos las bases 2 y 3, los números que pueden pasar el test siendo compuestos son muchos menos. Y si tomamos más bases todavía, los resultados mejoran considerablemente. Por ejemplo, sólo hay un pseudoprimo fuerte para las bases 2, 3, 5 y 7 menor que 25·109, y este número es 3,215,031,751.

    La sucesión de los números impares más pequeños que pasan el test de Miller-Rabin usando los primeros k números primos para k = 1, 2, 3,…  está dada por 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, … (Sloane A014233; Jaeschke 1993). Por lo tanto, el test es totalmente determinista si usamos los siete primeros números primos (con 8 no da ninguna mejora) para números menores menores de 3,4·10^14.

    Lo que se hace en la práctica para números muy grandes es tomar una serie de bases al azar y comprobar si se verifican las congruencias. Si no se verifica en algún caso, el número es compuesto con total seguridad. Si se verifican todas, hay una «sospecha» muy grande de que el número es primo, aunque no puede asegurarse. La probabilidad de error puede hacerse tan pequeña como se quiera con solo coger un número suficiente de bases.

Gracias a los trabajos de Pomerance, Selfridge y Wagstaff (1980) y Jaeschke (1993) podemos elaborar tests de rápida ejecución y completamente deterministas (usando Miller-Rabin) si consideramos números hasta un cierto tamaño:

• Para números menores que 25,326,001 basta probar con las bases 2, 3 y 5.
• Para números menores que 4,759,123,141 basta probar con las bases 2, 7 y 61.
• Para números menores que 2,152,302,898,747 basta probar con las bases 2, 3, 5, 7 y 11.
• Para números menores que 341,550,071,728,321 basta probar con las bases 2, 3, 5, 7, 11, 13 y 17.

     En 1980, Adleman publica un artículo titulado «On distinguishing prime numbers from composite numbers». Sus resultados son mejorados por Pomerance, Rumely, Cohen, H.W. Lenstra y A.K. Lenstra. Esta trabajo conjunto junto con el teorema que viene a continuación dan lugar a un test de primalidad conocido como APR (hay más de una versión de este test)

Teorema (Odlyzko-Pomerance, 1982): Existe una constante c>0 efectivamente computable tal que para todo n > ee existe un entero positivo t que satisface:
     i)  t es libre de cuadrados.
    ii)  0 < t < (log n)c·log(log(log n)) y tal que s(t) > √ n , donde s(t) = Π { q ∈ Z+ / q primo y q-1 divisor de t }

El test APR seguiría entonces los siguientes pasos:

Paso1: Introducimos un primo impar n.
Paso2: Buscamos (secuencialmente) un valor t que verifique s = s(t) > √ n.
Paso3: Factorizamos t. A sus factores pi les llamamos primos iniciales.
Paso4: Factorizamos s. A sus factores qi les llamamos primos euclídeos.
Paso5: Se comprueba que mcd (s·t, n) = 1 (si no es el caso, n no es primo)

Paso6: Para cada primo inicial p se tiene una de estas dos opciones:
    a)  np-1 ≠ 1 (mod p2)
    b)  np-1 ≡ 1 (mod p2) y para cada primo euclídeo q tal que p | q-1 existe un carácter ξ (aplicación de un grupo en el cuerpo de los números complejos) ξ: Zq* ——–> Gp de orden p y conductor q, tal que G(ξ)n ∈ η(ξ)n·G(ξn) módulo nZ[ξp, ξq] para algún 1 ≠ η(ξ) ∈ Gp (revisar)
    Si se da el caso a) probamos con otro primo inicial y si se da b) seguimos con el paso 7.

Paso7: Para cada i = 0, 1, 2, 3, … , t-1 se calcula mcd( ni (mod s) , n). Si alguno de los resultados obtenidos es un número comprendido estrictamente entre 1 y n entonces el número n es compuesto.

Si te parece interesante, puedes ver este video sobre los números primos:

Te damos la bienvenida a Sitios de I.E.S. Pintor José Hernández. Este es tu primer artículo. Edítalo o bórralo… ¡y comienza a publicar!