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!

Un comentario en “El primo más grande descubierto, y el algoritmo para encontrarlo

  1. Pingback: El teorema de la semana: el de los números primos – Series divergentes

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s