Los números primos más grandes que se conocen.  Método de Lucas-Lehmer

Primera publicación: 2005-03-11
 Último cambio: 2009-02-07
Los números de Mersenne son los que tienen la forma: 2n-1. 

Para que un número de Mersenne sea primo, el exponente n debe ser primo.  Lo contrario no es cierto, para la mayoría de exponentes primos, el número de Mersenne correspondiente no es primo.

Los números primos más grandes que se han encontrado son primos de Mersenne, esto es debido a dos motivos:

1.- En notación binaria estos números se representan con una hilera de unos tan larga como el exponente n , es decir, tienen una estructura muy simple.
2.- El test de Lucas-Lehmer permite certificar rápidamente la primalidad de estos números.

El test de Lucas-Lehmer dice que para todo p primo impar (es decir, exceptuando el 2), el número de Mersenne 2p-1 es primo si y solo si el resto de dividir Sp-1 entre 2p-1 es 0,  donde S1 = 4 y Sn+1 es el resultado de la congruencia (Sn2 - 2) mod (2p-1)

Por ejemplo, sea p = 5.  El número de Mersenne M5 es:  25 -1 = 31

La serie correspondiente es: S1 = 4, S2 = 14, S3 = 8*,  S4 = 62,  resto de dividir 62 entre 31 = 0, luego 31 es primo.  M5 es primo.

*194 mod 31 = 8.  La secuencia  de Sn se calcula módulo 2p-1 para ahorrar tiempo y espacio.
Pseudocódigo del test de Lucas-Lehmer:
Lucas_Lehmer_Test(p):
  s := 4;
  for i from 3 to p do s := s2-2 mod 2p-1;
  if s == 0 then
    2p-1 is prime
  else
    2p-1 is composite;
Implementación práctica del test de Lucas-Lehmer en Java (código fuente: LucasLehmer.java):
//Implementación del método de Lucas-Lehmer para calcular
//números primos de la forma 2^n - 1 (primos de Mersenne)
//v 1.10 - 2006-01-07
//Programado por: José Ángel González Rodríguez
//En un Pentium a 1133 MHz calcula los 13 primeros primos de Mersenne (aparte de M2)
//en menos de 2 segundos.

import java.math.BigInteger;

class LucasLehmer {

	static double start_time = System.currentTimeMillis();

	static double time_elapsed;

	static int np;

	public static void main(String args[]) {
		escribePrimosMersenne();
		time_elapsed = System.currentTimeMillis() - start_time;
		System.out.println("");
		System.out.println(np + " primos de Mersenne por el método de "
				+ "Lucas-Lehmer");
		System.out.println("Tiempo: " + time_elapsed / 1000 + " seg");
	}

	static int esPrimo(int n) {
		int rq = (int) Math.sqrt(n);
		for (int i = 2; i <= rq; i++) {
			if (n % i == 0)
				return 0;
		}
		return n;
	}

	static void escribePrimosMersenne() {
		for (int i = 3; i < 700; i++) {
			int n = esPrimo(i);
			if (n != 0) {
				BigInteger Mp = BigInteger.valueOf(2).pow(n);
				Mp = Mp.add(BigInteger.valueOf(-1));
				BigInteger s = BigInteger.valueOf(4);
				for (int j = 2; j < n; j++) {
					s = s.pow(2);
					s = s.add(BigInteger.valueOf(-2));
					s = s.mod(Mp);
					if (s.equals(BigInteger.valueOf(0))) {
						np++;
						System.out.println("");
						System.out.println("M" + n + " es primo");
						System.out.println("p=" + n + " M" + n + "=2^" + n
								+ "-1=" + Mp + " S" + j + "=" + s);
						break;
					}
				}
			}
		}
	}
}

Este programa chequea todos los exponentes primos desde 3 hasta 700.  En este rango hay 13 primos de Mersenne.

Gracias a que Java es capaz de operar con números enteros de precisión arbitraria (mediante la clase BigInteger), es fácil implementar el método de Lucas Lehmer para verificar la primalidad de números de Mersenne grandes.

El mismo programa de arriba una vez compilado: LucasLehmer.class.  Para ejecutarlo y calcular los 13 primeros primos de Mersenne (aparte de M2 que también es primo ya que 22-1 = 3, y 3 es primo) abre una ventana DOS y escribe:

java LucasLehmer

(recuerda que debes respetar mayúsculas y minúsculas y que no debes escribir la extensión .class).

Para que funcione debe estar instalado el Java Runtime Environment (JRE) adecuado a tu plataforma, en 32 ó 64 bits.  Es probable que ya lo tengas instalado.

En el caso de que quieras comprobar la primalidad de un número de Mersenne introduciendo tú el exponente primo, puedes usar el mismo programa ligeramente modificado: LucasLehmerInput.class, (código fuente: LucasLehmerInput.java).  Ten en cuenta que el tiempo de ejecución crece mucho para exponentes grandes.  Como antes, para ejecutarlo debes escribir en una ventana DOS:

java LucasLehmerInput

respetando mayúsculas y minúsculas y sin escribir la extensión .class.

Para dar una idea de la velocidad de este programa se adjunta la siguiente tabla de tiempos en segundos.  El cómputo ha sido realizado en un PC portátil normal adquirido en 2007, un Intel Core 2 duo T7100 a 1.8 GHz.
M11213 12 s
M21701 85 s
M44497 711 s
M86243 5091 s

Escríbeme si tienes alguna duda, mensaje o sugerencia.

Josechu
http://www.josechu.com/index_es.htm