Lucas-Lehmer-Test
# Lucas-Lehmer-Test

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 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: $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 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 $S(1)=4$ und $S(k+1)\equiv S(k)^{2}-2\ mod\ M_{p}$. Dann gilt: $M_{p}$ ist genau dann eine Primzahl, wenn $S(p-1)=0$.
Die Modulo-Funktion bzgl. einer Mersenne-Zahl lässt sich im Dualsystem (Binärsystem) besonders einfach berechnen, da die Mersenne-Zahl darin nur aus lauter Einsen bestehen.

## Beispiele

Beispiel 1: Wir prüfen mit diesem Verfahren, ob $M_{5}=2^{5}-1=31$ eine Primzahl ist:
Da $S(4)=0$ ist, ist $M_{5}=31$ eine Primzahl.
Beispiel 2: Wir prüfen, ob $M_{11}=2^{11}-1=2047$ eine Primzahl ist:
Da $S(10)>0$ ist, ist $M_{11}=2047$ keine Primzahl (es gilt $2047=23\cdot 89$).
Beispiel 3: Wir prüfen, ob $M_{19}=2^{19}-1=524287$ eine Primzahl ist:
Da $S_{18}=0$ ist, ist $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 $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_{11213}$ prim ist, dauerte dagegen mit einem damaligen Supercomputer Illiac II noch 2¼ Stunden.