Lucas-Lehmer-Test

Der Lucas-Lehmer-Test ist ein Primzahltest für Mersenne-Zahlen, das heißt für Zahlen der Form ${\displaystyle 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.

Ausschnitt von Seite 316 der Arbeit Théorie des Fonctions Numériques Simplement Périodiques von Édouard Lucas (1878)

Dieser Test beruht a​uf Eigenschaften d​er Lucas-Folgen u​nd nicht w​ie der Lucas-Test a​uf dem kleinen Fermatschen Satz.

Funktionsweise

Der Lucas-Lehmer-Test ist zum Testen von Mersenne-Zahlen ab ${\displaystyle M_{3}}$ geeignet. Er basiert ganz wesentlich darauf, dass die Mersenne-Zahlen im Dualsystem (Binärsystem) nur aus lauter Einsen bestehen.

Die Mersenne-Primzahl ist eine Primzahl, die ausschließlich mit der Binärziffer "1" geschrieben wird.
binär	11	111	11111	1111111	1111111111111	11111111111111111	1111111111111111111	1111111111111111111111111111111	…
potenz	2^2−1	2^3−1	2^5−1	2^7−1	2^13−1	2^17−1	2^19−1	2^31−1	…
dezimal	3	7	31	127	8.191	131.071	524.287	2.147.483.647	…
Die wichtigste Eigenschaft einer Mersenne-Primzahl: „Die Anzahl der Binärziffern muss eine Primzahl sein.“ Die Mersennezahl ${\displaystyle M_{n}}$ ist eine Dualzahl, die gerade aus ${\displaystyle n}$ Einsen besteht (Repunit, Zahlenpalindrom).

Der Lucas-Lehmer-Test funktioniert w​ie folgt:

Sei ${\displaystyle p}$ ungerade und prim. Die Folge ${\displaystyle S(k)}$ sei definiert durch ${\displaystyle S(1)=4,S(k+1)=S(k)^{2}-2}$.

Dann gilt: ${\displaystyle M_{p}=2^{p}-1}$ ist genau dann eine Primzahl, wenn ${\displaystyle S(p-1)}$ durch ${\displaystyle M_{p}}$ teilbar ist.[1]

Dieser Satz wurde 1930 von Derrick Henry 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 ${\displaystyle S(1)=4}$ und ${\displaystyle S(k+1)\equiv S(k)^{2}-2\ mod\ M_{p}}$. Dann gilt: ${\displaystyle M_{p}}$ ist genau dann eine Primzahl, wenn ${\displaystyle S(p-1)=0}$.

Beispiele

Beispiel 1: Wir prüfen mit diesem Verfahren, ob ${\displaystyle M_{5}=2^{5}-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 ${\displaystyle S(4)=0}$ ist, ist ${\displaystyle M_{5}=31}$ eine Primzahl.

Beispiel 2: Wir prüfen, ob ${\displaystyle M_{11}=2^{11}-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 ${\displaystyle S(10)>0}$ ist, ist ${\displaystyle M_{11}=2047}$ keine Primzahl (es gilt ${\displaystyle 2047=23\cdot 89}$).

Beispiel 3: Wir prüfen, ob ${\displaystyle M_{19}=2^{19}-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 ${\displaystyle S_{18}=0}$ ist, ist ${\displaystyle M_{19}=524287}$ eine Primzahl (dies ist schon seit 1603 bekannt).

Beispielimplementierung in Python

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 ${\displaystyle p}$ gerade oder nicht-prim ist, dies wird dem Nutzer überlassen. So würde das Programm bei Eingabe von ${\displaystyle p=2}$ die falsche Aussage liefern, dass die Zahl 3 keine Mersenne-Primzahl ist.

Briefstempel zur Entdeckung der Mersenne-Primzahl 2¹¹²¹³-1

Auf einem Intel Pentium 4 aus dem Jahr 2005 benötigt die Rechnung für ${\displaystyle p=11213}$ mit diesem Programm nur 41 Sekunden. Die Rechnung im Jahr 1963, mit der nachgewiesen wurde, dass ${\displaystyle M_{11213}}$ prim ist, dauerte dagegen mit einem damaligen Supercomputer Illiac II[2] noch 2¼ Stunden.[3]

#Lucas-Lehmer-Test fuer Python 3
print('Lucas-Lehmer-Test (Mersenne-Zahlen)')
p = int(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 {}eine Mersenne-Primzahl'.format('' if s == 0 else 'k'))

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, S. 289–321, ISSN 0002-9327 (dritter Teil der Abhandlung).
• Derrick Henry Lehmer: An extended theory of Lucas’ functions. In: The Annals of Mathematics. 31, No. 3, 1930, S. 419–448, ISSN 0003-486X.
  (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. ILLIAC II in der englischsprachigen Wikipedia
3. Donald B. Gillies: Three new Mersenne primes and a statistical theory