Lucas-Lehmer

Fra Wikipedia, den frie encyklopædi

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.

Indholdsfortegnelse 1 Algoritmen 1.1 Definitioner 1.2 Forløbet 1.3 Implementering

[redigér] Algoritmen

[redigér] 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.

[redigér] 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

[redigér] 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².

Denne artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den. Du kan også give den en bedre beskrivelse.