Lucas-Test (Mathematik)

Aus Kefk.

Der Lucas-Test ist eine Verbesserung des Fermatschen Primzahltest des Mathematikers Edouard Lucas, der nochmal von Brillhart und Selfrige verbessert wurde.

Inhaltsverzeichnis

1 Fermatscher Primzahltest
2 Lucas-Test
3 Verbesserter Lucas-Test
4 Literatur

Fermatscher Primzahltest

Gegeben sei eine Zahl $N$ mit $N > 1$ , die auf Primalität zu prüfen sei. Nach dem Primzahltest entsprechend dem kleinen fermatschen Satz ist die Zahl $N$ keine Primzahl, wenn folgende Bedingung für eine Zahl $a$ mit $1 < a < N$ zutrifft:

$a^{N-1}\not\equiv 1 \mod N$

Der Fermat-Test liefert also niemals die Aussage, eine Zahl sei prim, sondern kann nur das Prim-Sein ausschließen. Etwa für die reduziblen Carmichael-Zahl liefert der Fermat-Test keine Aussage.

1891 modifizerte Edouard Lucas den Primzahltest:

Lucas-Test

Gegeben sei eine Zahl N mit N > 1, die auf Primalität zu prüfen sei. Nach dem Lucas-Test ist die Zahl N eine Primzahl, wenn ein $a$ mit $1 < a < N$ gefunden werden kann, für das folgende Bedingungen zutreffen:

$a^{N-1}\mod N \equiv\,\,\,1$
$a^m\mod N \not\equiv\,\,\,1$ für jedes $m < N-1\$ , das $N-1\$ teilt.

Da hier nur noch die $m$ getestet werden müssen, die echte Teiler von $N - 1$ sind, müssen hier erheblich weniger Rechenschritte ausgeführt werden. Dabei besteht aber das Problem, dass man die Zahl Primfaktorzerlegung von $N - 1$ kennen muss, was meistens auf eine aufwändige Faktorisierung von $N - 1$ hinaus läuft. Für Zahlen mit bestimmten Formen ist diese Methode aber sehr effizient. So z.B. beikonstruierten Zahlen der Form 2ⁿ+1.

Beispiel:

Für die zu testende Zahl N=2147483647 sind jetzt mit N-1 = 2147483646 = 2 * 3² * 7 * 11 * 31 * 151 * 331,

191 verschiedene m zu testen.

1967 haben Brillhart und Selfridge den Test flexibilisiert:

Verbesserter Lucas-Test

Gegeben sei eine Zahl N mit N > 1, die auf Primalität zu prüfen sei. Nach dem verbesserten Lucas-Test ist die Zahl N eine Primzahl, wenn es eine natürliche Zahl a mit 1 < a < N gibt, für die gilt: