Lucas-Lehmer

En Lucas-Lehmer-test kan vise om et mersennetal også er et primtal. Testen er opkaldt efter François Edouard Anatole Lucas og Derrick Henry Lehmer. En nødvendig (men ikke tilstrækkelig) betingelse for at et mersennetal kan være et primtal er at eksponenten er et primtal.

Algoritmen

Definitioner

• p er et primtal.
• M(p) er et mersennetal med p som eksponent.
• s er det resultat, der viser om M(p) er et primtal.

Forløbet

1. s = 4
2. Gentag p-2 gange:
   • s = (s²-2) mod M(p)
3. Hvis s er 0 er M(p) et primtal

Implementering

Hvis algoritmen bruges direkte i et computerprogram, er den ikke særlig effektiv, selvom den er langt hurtigere end en generel primtalstest. Det er dog muligt, at lave en del optimeringer. I det binære talsystem skrives 2^p med et ettal efterfulgt af p nuller. Det betyder, at tallet kan findes ved at forskyde 1 p bits og derefter trække en fra.

Når s skal beregnes modulo p, kan man også udnytte, at tallet består af ene ettaller i totalssystemet.

Den store tidsrøver i denne algoritme er beregningen af S².

Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.