Lucas-Lehmer

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

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

Definitioner[redigér | redigér wikikode]

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

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

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 2p 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².

Matematik Stub
Denne artikel om matematik er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.