Logo

Mersenneprimtalstester

Her kan du teste om et mersennetal, der har formen 2n-1, også er et primtal. Mersennetal skrives ofte på en kort form, hvor M(n) betyder 2n-1. Hvis n er et sammensat tal, vil det tilsvarende mersennetal også være det. Den anvendte test kaldes Lucas-Lehmer-testen og den er opkaldt efter de matematikere, der udviklede den.

Testen er meget tidskrævende, så hvis du tester eksponenter over 10000 skal du være lidt tålmodig.

Din browser kan ikke vise mersenne-testeren. Det kan der være flere grunde til.

  • Din browser understøtter ikke java i version 1.2.
  • Java er deaktiveret af hensyn til sikkerheden.
  • Browseren understøtter ikke <object/>

Testen af en eksponent, n, sker i følgende trin:

  1. Det undersøges om n er et primtal. Hvis det ikke er det, er M(n) heller ikke et primtal.
  2. Det undersøges om M(n) har en divisor, udover 1, der er større end n og mindre end 4*n. De undersøgte tal har formen 2*k*n+1, hvor k er et heltal.
    1. Beregn D = 2*k*n+1
    2. Hvis D er et sammensat tal, er det ikke en divisor.
    3. Hvis D mod 8 giver 1 eller 7 er der måske tale om en divisor, og divisionen M(n)/D gennemføres.
  3. Hvis der er fundet en divisor, er M(n) et sammensat tal, og der laves ingen Lucas-Lehmer-test.
  4. S sættes til 4.
  5. Følgende gentages n-2 gange:
    1. S = S*S-2 modulo M(n)
  6. Hvis S er lig 0, er M(n) et primtal.

Punkterne 1 til 3 er ikke en del af selve Lucas-Lehmer testen, men er med for at undgå en test, der med sikkerhed vil vise, at M(n) er et sammensat tal. Hvis M(n) har en divisor udover 1 og M(n) er den mindst n.

Her er kildekoden til testeren.

Hvis du vil gøre mere ud af det, kan du hente kildekoden til en mersenne-tester til linux. Koden til dette program er muligvis nemmere at gennemskue end koden til appletten. Der findes også et optimeret program til flere styresystemer.


Tilbage til toppen af siden.
Tilbage til hovedmenuen.