Grandes primos
La moderna encriptaci¨®n requiere el uso de n¨²meros primos cada vez mayores; pero, de momento, no parece que vaya a fallar el suministro
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...
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? ¨C 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? ¨C 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???)? ¨C 1, un n¨²mero de 79 d¨ªgitos. El otro gran primo conocido no-M es 391581x2?????? ¨C 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? ¨C 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.