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^{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

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.

Dieser Satz wurde 1930 von Derrick Lehmer gefundenen 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).

Pythonprogramm

Umsetzung des Lucas-Lehmer-Test in ein Pythonprogramm (in der Programmiersprache Python kann mit beliebig großen ganzen Zahlen gerechnet werden, Grenzen setzt lediglich der verfügbare Speicher).

Auf einem Intel Pentium 4 von 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 auf einem Supercomputer Illiac II (siehe en.wikipedia Illiac II) noch 2¼ Stunden (siehe Donald B. Gillies: Three new Mersenne primes and a statistical theory).

#!/Lucas-Lehmer-Test
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 s==0:
    print 'eine',
else:
    print 'keine',
print 'Mersenne-Primzahl'

Literatur

• Paulo Ribenboim: Die Welt der Primzahlen, Springer Verlag, 1996
• Édouard Lucas: Théorie des Fonctions Numériques Simplement Périodiques, American Journal of Mathematics 1, 289–321, 1878 (dritter Teil der Abhandlung)
• Derrick Lehmer: An extended theory of Lucas’ functions, Ann. of Math. 31, 419–448, 1930
  (erste Seite seiner Doktorarbeit von 1930 in einer Ausstellung in Berkeley sowie weitere Photos)