Lucas-Lehmer-Test

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ⁿ − 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

Der Lucas-Lehmer-Test ist zum Testen von Mersenne-Zahlen ab M₃ 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.

Dann gilt: M_p = 2^p–1 ist genau dann eine Primzahl, wenn S(p–1) durch M_p teilbar ist.^[1]

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

Sei S(1) = 4, S(k+1) ≡ S(k)²–2 mod M_p. Dann gilt: M_p ist genau dann eine Primzahl, wenn S(p–1) ≡ 0 mod M_p.

Beispiele

Beispiel 1: Wir prüfen mit diesem Verfahren, ob M₅ = 2⁵–1 = 31 eine Primzahl ist:

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

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

Beispiel 2: Wir prüfen, ob M₁₁ = 2¹¹–1 = 2047 eine Primzahl ist:

 S( 1) = 4
 S( 2) = (   4² - 2) mod 2047 =   14
 S( 3) = (  14² - 2) mod 2047 =  194
 S( 4) = ( 194² - 2) mod 2047 =  788
 S( 5) = ( 788² - 2) mod 2047 =  701
 S( 6) = ( 701² - 2) mod 2047 =  119
 S( 7) = ( 119² - 2) mod 2047 = 1877
 S( 8) = (1877² - 2) mod 2047 =  240
 S( 9) = ( 240² - 2) mod 2047 =  282
 S(10) = ( 282² - 2) mod 2047 = 1736

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

Beispiel 3: Wir prüfen, ob M₁₉ = 2¹⁹–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 M₁₉ = 524287 eine Primzahl (dies ist schon seit 1603 bekannt).

Beispielimplementierung in Python

Im folgenden wird der Lucas-Lehmer-Test in Python implementiert. Der Vorteil der Programmiersprache Python ist hier, dass es mit beliebig großen ganzen Zahlen rechnen kann – Grenzen setzt lediglich der verfügbare Speicher. 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.

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 M₁₁₂₁₃ 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

• Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer Verlag, Berlin u. a. 2006, ISBN 3-540-34283-4 (Springer-Lehrbuch).
• Édouard Lucas: Théorie des Fonctions Numériques Simplement Périodiques. In: American Journal of Mathematics. 1, No. 4 , 1878, ISSN 0002-9327, S. 289–321 (dritter Teil der Abhandlung).
• Derrick Lehmer: An extended theory of Lucas’ functions. In: The Annals of Mathematics. 31, No. 3, 1930, ISSN 0003-486X, S. 419–448.
  (erste Seite seiner Doktorarbeit von 1930 in einer Ausstellung in Berkeley sowie weitere Photos).

Einzelnachweise

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