Grandes primos

La primera secuencia de la semana pasada la completan los números 25, 35 y 49, pues se trata de todos los productos posibles de dos números primos de una cifra, o sea, 2, 3, 5 y 7, ordenados de menor a mayor: 2x2, 2x3, 3x3, 2x5, 2x7, 3x5, 3x7, 5x5, 5x7 y 7x7.

La segunda secuencia es análoga a la anterior, solo que ahora se trata de los productos de dos factores de los primos de dos cifras menores de 20, o sea, 11, 13, 17 y 19, por lo que los números que completan la secuencia son 289, 323 y 361 (17x17, 17x19 y 19x19).

En cuanto a los números a descomponer en dos factores primos, se factorizan así:

2117 = 29x73

4087 = 61x67

7387 = 83x89

9167 = 89x103

Quien haya intentado descomponerlos “a pelo” se habrá dado cuenta de la dificultad de este tipo de factorizaciones incluso en casos relativamente sencillos.

Los primos de más de una cifra (lo que excluye a los atípicos 2 y 5) solo pueden terminar en 1, 3, 7 o 9, por lo que el producto de dos de ellos cualesquiera también terminará en uno de estos cuatro números.

Números de Mersenne

La idoneidad de los números primos para las tareas de encriptación tiene que ver con la dificultad -por no decir imposibilidad- de abordarlos mediante fórmulas o algoritmos simples: solo sucumben -cuando lo hacen- ante la fuerza bruta de comprobaciones y cálculos exhaustivos. Pero, dada la enorme capacidad de cálculo de los modernos ordenadores, solo los primos muy grandes se les resisten todavía.

¿Y cuán grandes son los números primos de los que disponemos? Enormes, muy por encima de las necesidades de la criptografía actual, que maneja primos de “solo” unos cientos de dígitos, cuando ya los conocemos de varios millones.

Los mayores números primos conocidos son números de Mersenne, es decir, de la forma 2ⁿ – 1, denominados así en honor de su descubridor, el matemático y filósofo francés Marin Mersenne (1588-1648). El mayor primo de Mersenne conocido es aquel en el que n = 82589933, que es un número con casi 25 millones de dígitos.

Los números de Mersenne suelen expresarse de la forma Mn, donde n es el exponente de 2 en la fórmula 2ⁿ – 1. Hasta mediados del siglo pasado, el mayor primo conocido (descubierto en 1876) era M₁₂₇, un número de 39 dígitos. En 1951 se encontró uno de los dos grandes primos conocidos que no es exactamente un número de Mersenne, aunque está basado en el anterior: 180x(M₁₂₇)² – 1, un número de 79 dígitos. El otro gran primo conocido no-M es 391581x2²¹⁶¹⁹³ – 1, un número de 65087 dígitos.

La secuencia de los números de Mersenne, para n = 0, 1, 2, 3, 4, 5, 6…, es: 0, 1, 3, 7, 15, 31, 63…

Evidentemente, no todos son primos. Como entre los siete primeros solo hay dos números compuestos (15 y 63), cabría sospechar que muchos sí lo son, pero en realidad la inmensa mayoría de los números de Mersenne no son primos (tan es así que se llegó a creer que los primos de Mersenne eran finitos). Invito a mis sagaces lectoras y lectores a investigar para qué valores de n la expresión 2ⁿ – 1 puede o no puede dar lugar a un número primo.

Otrosí: ¿Cuántos primos de Mersenne hay menores de 100? ¿Y menores de 200?

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aquí para recibir nuestra newsletter semanal.