Appendix C - Mersenne-priemgetallen

Lucas-Lehmer-test ][ Mersenne-priemgetallen

Lucas-Lehmer-Test
Om vast te stellen of het Mersenne getal M(p) een priemgetal is, onder voorwaarde dat p een oneven priemgetal is, wordt tegenwoordig vaak gebruik gemaakt van de Lucas-Lehmer-Test.
In deze test wordt gebruik gmaakt van een rij getallen L₁, L₂, L₃, ... die als volgt is gedefinieerd

L₁ = 4
L_{n + 1} = (L_n² - 2) mod (2^{^p}- 1)

Onder deze voorwaarden is
2^{^p}-1 is een priemgetal Û L_p-1 = 0
Op basis van deze rij hebben we in Maple de volgende functie.

> restart:
> llt:=proc(p)
>   # Lucas-Lehmer-Test voor Mersenne-priemgetallen
>   local L, i;
>   L:=4;
>   for i from 3 to p do
>     L:=(L^2-2) mod (2^p-1);
>   od;
>   if L = 0 then
>     1 # `2^q-1 is priem`;
>   else
>     0 # `2^q-1 is samengesteld`;
>   fi;
> end:

Is de functie waarde 1 dan hebben we een priemgetal dat een Mersenne-priemgetal oplevert; is de functiewaarde 0, dan is dat niet het geval.

De volgende 10 oneven priemgetallen 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 leveren het 2e tot en met het 11e Mersenne-priemgetal.
We controleren dit aan de hand van de variabele SOM, die telkens met 1 verhoogd wordt, als we te maken hebben met een priemgetal dat een Mersenne-priemgetal genereert.

> prij:=[3,5,7,13,17,19,31,61,89,107]:
> SOM:=0:
> for i to 10 do
>   p:=prij[i];
>   SOM:= SOM + llt(p);
> od:
> SOM;

We hebben dus inderdaad te maken met 10 Mersenne-priemgetallen: het 2e tot en met het 11e.

> for i to 10 do
>   p:=prij[i];
>   print(2^p-1);
> od:

7
31
127
8191
131071
524287
2147483647
2305843009213693951
618970019642690137449562111
162259276829213363391578010288127

Het ontbinden van getallen in Maple, als die getallen nogal grote priemfactoren hebben, verloopt bijzonder langzaam. Met bovenstaande Lucas-Lehmer-Test vinden we relatief snel resultaat.
Het door Mersenne zelf genoemde priemgetal 257 levert

> M257:=2^257-1;

M257 := 231584178474632390847141970017375815706539969331281128078915168015826259279871

Ook blijkens de Lucas-Lehmer-Test (we hadden dit resultaat al eerder gezien) is M257 geen priemgetal.

> llt(257);

[mersenne_c.htm] laatste wijziging op: 30-11-2002