El primo más grande descubierto, y el algoritmo para encontrarlo

primote — Un muestra de sus más de 22 millones de dígitos.

La semana pasada el proyecto GIMPS (Great Internet Mersenne Prime Search) anunció el descubrimiento de otro número primo de Mersenne: $2^{74,207,281}$ . Este número primo tiene 22,338,618 dígitos, y fue descubierto por Curtis Cooper, de la Universidad de Missouri Central. La noticia ya ha sido discutida en varios blogs matemáticos [1, 2, 3, 4, 5, por ejemplo] y en el resto de la prensa [1, 2, 3, 4, por ejemplo]. El anterior primo de Mersenne, $2^{57,885,161}-1$ , fue descubierto hace casi tres años por el mismo Cooper.

Cooper verificó la primalidad de $2^{74,207,281}$ usando el software de GIMPS en una PC con un procesador Intel i7-4790, y el cálculo tomó 31 días. Aunque su computadora reportó la primalidad de este número desde septiembre pasado, no fue sino hasta el 7 de enero cuando GIMPS detectó el descubrimiento. La primalidad fue verificada dos veces más con computadoras y software distintos.

Los números primos de Mersenne son los de la forma $2^p-1$ , donde p es un entero positivo. Por ejemplo, $2^2-1=3$ y $2^3-1 = 7$ son primos de Mersenne, aunque $2^4 - 1 = 15$ no es primo. De hecho, no es difícil ver que, si p no es primo, entonces $2^p-1$ no puede ser primo, porque si $p=ab$ , con $a,b>1$ , entonces

$2^p-1 = 2^{ab} - 1 = (2^a - 1)(2^{a(b-1)} + 2^{a(b-2)} + \ldots + 1)$

es una factorización de $2^p-1$ . Así, vemos que $2^6-1, 2^8-1$ o $2^9-1$ no son primos, por ejemplo. La importancia de los números primos de Mersenne radica en el hecho que, si $2^p-1$ es primo, entonces el número $2^{p-1}(2^p-1)$ es perfecto: es igual a la suma de sus divisores. Aquí en Series divergentes ya hemos hablado sobre los números perfectos, y de hecho demostramos que los únicos números perfectos pares son precisamente los de la forma $2^{p-1}(2^p-1)$ , si $2^p-1$ es primo.

Ahora bien, si p es primo, no necesariamente $2^p-1$ lo es, como lo muestra el ejemplo $2^{11}-1 = 2047 = 23\times89$ . De hecho, los números de Mersenne son cada vez más raros: $2^{74,207,281}$ es apenas el 49no conocido, y solo hay 44 primos de Mersenne hasta el número $2^{33,219,253}-1$ .

El software de GIMPS verifica la primalidad de un número de la forma $2^p-1$ utilizando el algoritmo de Lucas y Lehmer, que consiste en construir la sucesión de Lucas $v_{k\phantom{\;}}$ definida como

$v_0 = 4, \qquad v_{k+1} = v_{k}^2 - 2 \pmod{2^p-1}$ ,

y verificar si $2^p-1$ divide a $v_{p-2}$ . Con $\pmod{2^p-1}$ nos referimos al residuo de dividir entre $2^p-1$ . Así de fácil.

Por ejemplo, si $p=7$ , $2^p-1 = 127$ y entonces la sucesión de Lucas es

$v_0 = 4$ ,
$v_1= 4^2-2=14$ ,
$v_2=14^2-2=194\equiv 67 \pmod{127}$ ,
$v_3=67^2-2=4487\equiv 42 \pmod{127}$ ,
$v_4=42^2-2=1762\equiv 111 \pmod{127}$ ,
$v_5=111^2-2=12319\equiv 0\pmod{127}$ .

Como 127 divide a $v_5=12319$ , entonces concluimos que 127 es primo.

El algoritmo de Lucas-Lehmer es definitivo: $2^p-1$ es primo si y solo si divide a $v_{p-2}$ . La demostración de este resultado, aunque no es muy difícil, es un poco técnica como para este blog. Puede ser consultada, entre otros, en el texto de Richard Crandall y Carl Pomerance, Prime Numbers: A Computational Perspective, donde se sigue del siguiente criterio, conocido como el criterio «n+1» de Lucas-Lehmer.

Fijamos dos números enteros a, b y definimos $f(x)=x^2-ax+b$ , $\Delta=a^2-4b$ , y la sucesión

$V_k=x^k+(a-x)^k\pmod{f(x)}$ .

Tenemos el siguiente teorema.

Teorema. Sea n un entero positivo primo relativo con 2b y tal que el símbolo de Jacobi de Δ y n es $(\frac{\Delta}{n})=-1$ . Si F es un divisor par de n+1, n divide a $V_{F/2}$ , y $V_{F/2q}$ es primo relativo a n para todos los primos impares q que dividen a F, entonces todo primo p que divide a n satisface que $p\equiv(\frac{\Delta}{p})\pmod F$ . En particular, si $F>\sqrt n+1$ , entonces n es primo.

Si $n=2^p-1$ , entonces las condiciones del teorema se satisfacen tomando $a=4, b=1$ , de tal forma que $f(x)=x^2-4x+1$ y $\Delta=12$ . Como $n+1=2^p$ , si tomamos $F=2^{p-1}$ entonces F no tiene divisores primos impares, y entonces es suficiente con verificar que

$V_{F/2} = V_{2^{p-2}} \equiv 0 \pmod{2^p-1}$ .

Ahora bien, como $f(x)=x(x-4)+1$ , entonces $x(4-x)\equiv 1\pmod{f(x)}$ , y por lo tanto, para cada m,

$V_{2m} = x^{2m}+(4-x)^{2m} = (x^m+(4-x)^m)^2-2x^m(4-x)^m$
$\equiv (x^m + (4-x)^m)^2 - 2 = V_m^2-2 \pmod{f(x)}$ .

Por lo tanto, $V_{2^k} = v_k$ , y entonces solo debemos verificar que $v_{p-2} \equiv 0 \pmod{2^p-1}$ .

Cualquier persona puede participar en GIMPS. Solo necesita una computadora, registrarse en GIMPS e instalar el software necesario. Además, hay un premio de $3,000.00 dólares para quien encuentre el siguiente número primo, y uno de $50,000.00 dólares para quien encuentre el primer primo de más de 100 millones de dígitos. ¡Éntrenle!

El primo más grande descubierto, y el algoritmo para encontrarlo

2 comentarios sobre “El primo más grande descubierto, y el algoritmo para encontrarlo”

Deja un comentario Cancelar la respuesta

Sharéalo:

Relacionado

2 comentarios sobre “El primo más grande descubierto, y el algoritmo para encontrarlo”

Deja un comentario Cancelar la respuesta