Primos muy lejanos

El primo más grande de todos

El 26 de diciembre de 2016, Jonathan Pace, parte del equipo GIMPS (Great Internet Mersenne Prime Search en inglés, o Gran Búsqueda Internet de Primos de Mersenne), anunció haber encontrado el 50mo primo de Mersenne conocido hasta ahora: 

2^(77,232,917) - 1

Un número de 23,249,425 dígitos que tiene el nuevo récord de el primo más grande conocido hasta ahora. Si quieres sorprender a la gente en tus fiestas, puedes memorizar los dígitos descargando el número en este enlace. 

¿Por qué estamos buscando primos tan gigantes? ¿Quién es Mersenne y quiénes son sus primos? ¿Quién es esa gente de GIMP? ¿Hay infinitos primos de Mersenne? En esta entrada te damos las respuestas a todas estas preguntas -excepto la última-.  

Mersenne y sus primos

Marin Mersenne, un monje francés, era una especie de facebook académico de principios del siglo XVII, ayudando a conectar a grandes científicos, matemáticos y pensadores de la época. En particular, tuvo una prolífica correspondencia con un tal Pierre de Fermat que tal vez les suena conocido.

Fermat estaba tratando de encontrar una fórmula que le pudiera dar únicamente números primos y le escribió a Mersenne sobre los que hoy conocemos como Números de Fermat.

El n-ésimo número de Fermat es el resultado de elevar 2 a la 2^n potencia, y luego sumarle 1. Como ves en la tabla de arriba, son números que crecen muy rápidamente, por lo que rápidamente se vuelven difíciles de calcular (sobre todo en el siglo diecisiete). Fermat conjeturó que todos los números de esta forma serían primos y efectivamente los 5 primeros así lo son.

En 1732, Euler demostró que el siguiente número de Fermat, F5 = 4,294'967,297 no era un número primo. (No es difícil imaginar que Fermat conocía quién es F5, porque no es tan grande, simplemente no calculó su descomposición en primos porque qué flojera. Esto es importante en nuestra historia.)

4,294'967,297 = 641 x 6'700,417

Hasta la fecha se conoce la factorización de los primeros 12 números de Fermat y, entre ellos, únicamente los primeros 5 originales son primos. No sabemos si hay más primos de Fermat, si son los únicos, si pudieran ser infinitos. 

En su correspondencia, Mersenne quiso ir uno más que Fermat. O, más bien, uno menos. Mersenne era músico y sabía que la nota anterior a un armónico es mucho muy disonante. Cambiando armónico por múltiplo y disonante por primo, esto le dio algo de intuición sobre cómo moverle. 

En lugar de sumarle uno, como Fermat, Mersenne le restó uno. Estos números crecen a una velocidad mucho menor, de manera que Mersenne pudo darse cuenta que no todos eran primos. De hecho, Mersenne pudo darse cuenta que si el exponente de 2 no era primo, el resultado no tenía manera de ser primo tampoco. Mersenne conjeturó que hasta el 257, los únicos primos de Mersenne serían para n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 serían los únicos primos. 

Fue una conjetura más o menos: ni 67 ni 257 son primos y omitió 61, 89 y 107, que sí generan números primos. Aunque no crece tan rápido como los números de Fermat, calcular M257 era impensable en aquellos tiempos. 

Mersenne y la internet

Es relativamente complicado decidir si un número muy grande es primo o no. Claro, debe ser impar y no puede terminar en 5. Hacer las primeras pruebas de divisibilidad no es demasiado complicado pero para números de 30, 40 o 60 dígitos se vuelve una tarea imposible, incluso computacionalmente. Es todavía mucho más difícil encontrar la factorización en primos de un número. (Y de rato explicaremos por qué es bueno.) Es decir: hay pruebas que nos permiten asegurar que un número no puede ser primo mucho antes de saber qué números lo dividen. 

Sin embargo, existe una prueba en particular que permite saber si un número de Mersenne tiene chance de ser primo, que elimina muchos candidatos rápidamente sin necesidad de hacer tantas pruebas. Si pasa la primera prueba, entonces sí se le hacen todas las demás. Por eso, entre los 10 primos más conocidos más grandes, 9 son números de Mersenne. 

Esto ha motivado una gran búsqueda del tesoro en internet. GIMPS es un proyecto de colaboración mundial para compartir poder de cómputo: descargas un código y se te asignan ciertos valores de n. Puedes dejar tu compu corriendo mientras vas al trabajo. De esta manera se han verificado todos los exponentes hasta 42 millones, probado al menos una vez todos los exponentes hasta 76 millones, y se han encontrado 15 números primos de Mersenne, incluyendo al más reciente hace menos de un mes. 

El número 2^(77,232,917) - 1 recibió tentativamente el número 50, aunque hace falta verificar muchos exponentes entre 42 millones y 76 millones. 

¿Y para qué buscamos primos tan grandes?

Ya desde Euclides sabemos que hay infinitos números primos de modo que qué sentido tiene encontrar primos cada vez más grandes. Bueno, hay un par de respuestas. Primero: a los humanos nos gusta eso de batir récords. Encontrar el siguiente primo más grande es una manera de pasar a la historia, incluso en proyectos colaborativos como GIMPS, aunque sea un ratito y como trivia. Además, existen varios premios en efectivo a la primera persona que encuentre un número primo de más de 1 millón, 10 millones, 100 millones y 1000 millones de dígitos (las primeras dos ya se entregaron). 

Segundo: nuestra seguridad en internet depende en gran medida de nuestro repertorio de números primos muy grandes. El método más famoso de criptografía de llave pública es el llamado RSA, que descansa en lo difícil que es no solo saber si un número es primo o no sino, sobre todo, conocer cuáles son sus factores primos. Los fundadores (ahora millonarios) han establecido una serie de retos sobre específicos de 174, 193, 212, 232, 270, 309, 463 y 617 dígitos. El primero que encuentre los dos factores primos (se sabe que son solo 2) podría reclamar hasta 200mil dólares. 

Mucho peor: el primero que encuentre un algoritmo rápido y eficiente para encontrar la factorización en primos de números muy, muy grandes podría poner en jaque a todo nuestro sistema financiero.

Recientemente, la criptografía se ha movido también hacia otros algoritmos y no únicamente el RSA. Actualmente es muy popular la criptografía de curvas elípticas, pues encriptar requiere mucho menor poder de procesamiento que RSA, que es útil en aparatos móviles y comercio en línea.

De todos modos, es lindo tener algo qué contestar cuando la gente pregunta: ¿Para qué sirven las matemáticas?