A principios de diciembre de 2016, diversos medios de comunicación, entre ellos el número 515 del Boletín de la RSME, nos informaban del descubrimiento de un primo de 9 millones de dígitos (véase también: quo).
A algunos de los que nos interesan más los récords de teoría de números computacional que los de natación en piscina olímpica (y bañador sin poliuretano, por supuesto), que el hallazgo de un primo de 9 millones de dígitos fuese noticia nos parecía raro, dado que desde hace 10 años se conocen primos de mayor tamaño. Al escribir esto, el mayor primo conocido es \(2^{74\,207\,201}-1\) (un primo de Mersenne), que fue descubierto en enero de 2016 por Curtis Cooper dentro del Internet Mersenne Prime Search (GIMPS), y tiene \(22\,338\,618\) dígitos.
Así pues, ¿qué interés tenía el primo de 9 millones de dígitos para que nos hablaran de él en medios generalistas? Explicarlo requiere algo más que recurrir sólo al tamaño, y es lo que vamos a hacer aquí.
Los primos de la forma \(2^{2^n}+1\) se denominan primos de Fermat (sólo se conocen cinco, los correspondientes a \(n=0,1,2,3,4\)), y los de la forma \(2^p-1\) primos de Mersenne (en este momento se conocen \(49\), y a menudo el mayor primo conocido es uno de este tipo). Existen tests especializados para probar la primalidad o no de tales tipos de números: el test de Pépin y el test de Lucas-Lehmer, respectivamente. Menos conocidos son los denominados primos de Proth, que son los de la forma \(k \cdot 2^n+1\) (con \(k<2^n\)), cuya primalidad se puede analizar con el denominado test de Proth, que es similar a los de Pépin y Lucas-Lehmer. La existencia de estos tests especializados (los detalles de cómo son se pueden consultar, por ejemplo, en mi libro sobre teoría de números [2]) hacen que se puedan encontrar primos de estos tipos de tamaño muchísimo mayor que los primos «normales y corrientes» para los que no hay tests específicos.
Por cierto, una aclaración: aunque los primos «grandes» son muy útiles en criptografía, los que ahí se requieren son de cientos de dígitos; estos primos de millones de dígitos no tienen actualmente ninguna aplicación criptográfica. Pero, aun así, estar al tanto del avance de los algoritmos de primalidad y -sobre todo- de factorización de enteros es importante para los que se dedican a la ciberseguridad (un avance espectacular e inesperado en los algoritmos de factorización podría ocasionar un gran desastre en este campo). Y siempre se puede decir que el trabajo computacional necesario (a menudo meses de cálculo en un ordenador doméstico) para comprobar la primalidad de tales números es muy útil para verificar la potencia y fiabilidad de los ordenadores.
Pero dejemos eso y volvamos a los números de Proth. En realidad, a los números de Sierpinski, con los que están íntimamente relacionados. Un número de Sierpinski es un entero positivo impar \(k\) tal que todos los números del conjunto
$$
\{k \cdot 2^n+1 : n \in \mathbb{N}\}
$$
son compuestos (véase [1] o nota 3.23, página 208 de [2]). Su nombre alude al matemático polaco Waclaw Sierpinski (1882-1969), quien en 1960 probó que existen infinitos \(k\) con tal propiedad. No se conocen muchos números de Sierpinski; al escribir esto, los más pequeños que se han encontrado son
$$
78\,557,\ 271\,129,\ 271\,577,\ 322\,523,\ 327\,739.
$$
Fue John Selfridge (1927-2010) en 1962 quien probó que \(78\,557\) es un número de Sierpinski; logró demostrar que, cuando \(k = 78\,557\), todos los números de la forma \(k \cdot 2^n+1\) tienen un divisor en el conjunto \(\{3, 5, 7, 13, 19, 37, 73\}\).
Determinar el menor número de Sierpinski es un problema abierto, el denominado problema de Sierpinski. En 1967, Sierpinski y Selfridge conjeturaron que \(k = 78\,557\) era el menor número de Sierpinski, lo cual resolvería el problema. Para probarlo, hay que ver que todos los \(k\) impares menores que \(78\,557\) no son números de Sierpinski; es decir, que para cada uno de ellos existe un \(n\) tal que \(k \cdot 2^n + 1\) es primo. En 2002 se inició una búsqueda intensiva (colaborando a través de internet) para descartar todos esos \(k < 78\,557\); en ese momento quedaban diecisiete candidatos por eliminar, y el proyecto se denominó Seventeen or Bust.
En poco tiempo se descartaron muchos candidatos, y en 2007 ya se habían reducido a estos seis:
$$
10\,223,\ 21\,181,\ 22\,699,\ 24\,737,\ 55\,459,\ 67\,607.
$$
Parecía que el problema de Sierpinski podría ser resuelto en no mucho tiempo pero, desde entonces, y pese a que la búsqueda colaborativa por internet no sólo continuó sino que se intensificó (se integró en otro proyecto más amplio de búsqueda distribuida de primos denominado PrimeGrid, con miles de usuarios de todo el mundo), no había habido avances. Hasta que, el 31 de octubre de 2016, el húngaro Szabolcs Péter, uno de los participantes en el proyecto PrimeGrid, demostró que
$$
10\,223 \cdot 2^{31\,172\,165}+1
$$
es un número primo (con \(9\,383\,761\) dígitos, el séptimo en el ranquin actual de tamaño de números primos, y el mayor primo conocido que no es de Mersenne). Tras la correspondiente verificación por otros participantes de PrimeGrid, el anuncio oficial del hallazgo tuvo lugar un mes más tarde. Este descubrimiento elimina la posibilidad de que \(k=10\,223\) sea un número de Sierpinski, y ya sólo queda descartar cinco más para que la conjetura de Sierpinski y Selfridge se convierta en un teorema.
Referencias
[1] W. Sierpinski,
Sur un probléme concernment les nombres $k \cdot 2^n +1$,
Elem. Math. 15, 63-74, 1960.
[2] J. L. Varona,
Recorridos por la Teoría de Números,
Electolibris y Real Sociedad Matemática Española,
Colección Textos Universitarios, núm. 4,
Murcia, 2014.
Dejar una contestacion