Lucas-Lehmer-Test

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel beschreibt einen Primzahltest für Mersenne-Zahlen. Der allgemeine, auf dem kleinen Fermatschen Satz beruhende Primzahltest von Lucas ist im Artikel Lucas-Test erläutert.
Ausschnitt von Seite 316 der Arbeit Théorie des Fonctions Numériques Simplement Périodiques von Édouard Lucas (1878)

Der Lucas-Lehmer-Test ist ein Primzahltest für Mersenne-Zahlen, das heißt für Zahlen der Form M_n = 2^n - 1. Der Test wird im GIMPS-Projekt (engl.: Great Internet Mersenne Prime Search), der Suche nach bisher nicht bekannten Mersenne-Primzahlen, angewandt.

Dieser Test beruht auf Eigenschaften der Lucas-Folgen und nicht wie der Lucas-Test auf dem kleinen Fermatschen Satz.

Funktionsweise[Bearbeiten]

Der Lucas-Lehmer-Test ist zum Testen von Mersenne-Zahlen ab M3 geeignet. Er basiert ganz wesentlich darauf, dass die Mersenne-Zahlen im Dualsystem nur aus lauter Einsen bestehen und funktioniert wie folgt:

Sei p ungerade und prim. Die Folge S(k) sei definiert durch S(1) = 4, S(k+1) = S(k)2–2.
Dann gilt: Mp = 2p–1 ist genau dann eine Primzahl, wenn S(p–1) durch Mp teilbar ist.[1]

Dieser Satz wurde 1930 von Derrick Lehmer gefunden und geht auf Édouard Lucas zurück (siehe Abbildung). Mit Hilfe der Modulo-Funktion mod lässt sich der Satz so formulieren:

Seien S(1) = 4 und S(k+1) = S(k)2 – 2 mod Mp. Dann gilt: Mp ist genau dann eine Primzahl, wenn S(p – 1) = 0.

Beispiele[Bearbeiten]

Beispiel 1: Wir prüfen mit diesem Verfahren, ob M5 = 25–1 = 31 eine Primzahl ist:

 S(1) = 4
 S(2) = ( 4² - 2) mod 31 =  14 mod 31 = 14
 S(3) = (14² - 2) mod 31 = 194 mod 31 = 8
 S(4) = ( 8² - 2) mod 31 =  62 mod 31 = 0

Da S(4) = 0 ist, ist M5 = 31 eine Primzahl.

Beispiel 2: Wir prüfen, ob M11 = 211–1 = 2047 eine Primzahl ist:

 S( 1) = 4
 S( 2) = (   4² - 2) mod 2047 =      14 mod 2047 = 14
 S( 3) = (  14² - 2) mod 2047 =     194 mod 2047 = 194
 S( 4) = ( 194² - 2) mod 2047 =   37634 mod 2047 = 788
 S( 5) = ( 788² - 2) mod 2047 =  620942 mod 2047 = 701
 S( 6) = ( 701² - 2) mod 2047 =  491399 mod 2047 = 119
 S( 7) = ( 119² - 2) mod 2047 =   14159 mod 2047 = 1877
 S( 8) = (1877² - 2) mod 2047 = 3523127 mod 2047 = 240
 S( 9) = ( 240² - 2) mod 2047 =   57598 mod 2047 = 282
 S(10) = ( 282² - 2) mod 2047 =   79522 mod 2047 = 1736

Da S(10) > 0 ist, ist M11 = 2047 keine Primzahl (es gilt 2047 = 23·89).

Beispiel 3: Wir prüfen, ob M19 = 219–1 = 524287 eine Primzahl ist:

 S( 1) = 4
 S( 2) = (      4² - 2) mod 524287 =     14
 S( 3) = (     14² - 2) mod 524287 =    194
 S( 4) = (    194² - 2) mod 524287 =  37634
 S( 5) = (  37634² - 2) mod 524287 = 218767
 S( 6) = ( 218767² - 2) mod 524287 = 510066
 S( 7) = ( 510066² - 2) mod 524287 = 386344
 S( 8) = ( 386344² - 2) mod 524287 = 323156
 S( 9) = ( 323156² - 2) mod 524287 = 218526
 S(10) = ( 218526² - 2) mod 524287 = 504140
 S(11) = ( 504140² - 2) mod 524287 = 103469
 S(12) = ( 103469² - 2) mod 524287 = 417706
 S(13) = ( 417706² - 2) mod 524287 = 307417
 S(14) = ( 307417² - 2) mod 524287 = 382989
 S(15) = ( 382989² - 2) mod 524287 = 275842
 S(16) = ( 275842² - 2) mod 524287 =  85226
 S(17) = (  85226² - 2) mod 524287 = 523263
 S(18) = ( 523263² - 2) mod 524287 =      0

Da S(18) = 0 ist, ist M19 = 524287 eine Primzahl (dies ist schon seit 1603 bekannt).

Beispielimplementierung in Python[Bearbeiten]

Das folgende Programm implementiert den Lucas-Lehmer-Test in der Programmiersprache Python. In Python ist es möglich, mit beliebig großen ganzen Zahlen zu rechnen, die nur durch den verfügbaren Speicher begrenzt sind. Die hier vorgestellte Implementierung berücksichtigt nicht, dass der Lucas-Lehmer-Test idealerweise bereits abbricht, wenn p gerade oder nicht-prim ist, dies wird dem Nutzer überlassen. So würde das Programm bei Eingabe von p = 2 die falsche Aussage liefern, dass die Zahl 3 keine Mersenne-Primzahl ist.

Briefstempel zur Entdeckung der Mersenne-Primzahl 211213-1

Auf einem Intel Pentium 4 aus dem Jahr 2005 benötigt die Rechnung für p = 11213 mit diesem Programm nur 41 Sekunden. Die Rechnung im Jahr 1963, mit der nachgewiesen wurde, dass M11213 prim ist, dauerte dagegen mit einem damaligen Supercomputer Illiac II (siehe en:ILLIAC II) noch 2¼ Stunden.[2]

#Lucas-Lehmer-Test fuer Python 2.6/2.7
print 'Lucas-Lehmer-Test (Mersenne-Zahlen)'
p = int(raw_input ('Exponent p von 2^p-1 '))
m = 2**p-1
print 'm = 2 ^', p, '- 1 =', m
s = 4
for i in range (2, p):
    s = (s*s-2) % m
print 'ist',
if not s==0:
    print 'keine',
print 'Mersenne-Primzahl'

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Zum Beweis siehe Ribenboim: Die Welt der Primzahlen, S. 78/79.
  2. siehe Donald B. Gillies: Three new Mersenne primes and a statistical theory