Los números primos más grandes que se conocen. Método de Lucas-Lehmer |
|||||||||
Primera publicación: 2005-03-11 |
|||||||||
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. 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:
|
|||||||||
Implementación práctica del test de Lucas-Lehmer en Java (código fuente:
LucasLehmer.java):
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.
|
|||||||||
Escríbeme si tienes alguna duda, mensaje o sugerencia. |