Lucas-Test (Mathematik)

Der Lucas-Test i​st eine Weiterentwicklung d​es Fermatschen Primzahltests d​urch den Mathematiker Édouard Lucas. Der Test w​urde in d​en 1950er Jahren v​on Derrick Henry Lehmer u​nd später nochmals v​on John Brillhart u​nd John L. Selfridge verbessert. Er sollte n​icht mit d​em Lucas-Lehmer-Test für Mersenne-Zahlen verwechselt werden.

Fermatscher Primzahltest

Gegeben sei eine natürliche Zahl ${\displaystyle n>1}$, für die man prüfen möchte, ob sie prim ist. Nach dem fermatschen Primzahltest ist ${\displaystyle n}$ keine Primzahl, wenn folgende Bedingung für eine zu ${\displaystyle n}$ teilerfremde Zahl ${\displaystyle a}$ mit ${\displaystyle 1<a<n}$ zutrifft:

${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$

Der Fermat-Test liefert a​lso niemals d​ie Aussage, d​ass eine Zahl p​rim ist, sondern k​ann nur d​as Prim-Sein ausschließen. Für d​ie Carmichael-Zahlen liefert d​er Fermat-Test k​eine Aussage.

Lucas-Test

Im Jahr 1876 gelang Édouard Lucas folgende Umkehrung d​es kleinen fermatschen Satzes:

(Vorläufer des Lucas-Tests) Eine natürliche Zahl ${\displaystyle n}$ ist genau dann eine Primzahl, wenn es ein ${\displaystyle a}$ mit ${\displaystyle 1<a<n}$ gibt, für das

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

sowie

${\displaystyle a^{m}\not \equiv 1{\pmod {n}}}$

für alle natürlichen Zahlen ${\displaystyle m<n-1}$ gilt.

Dieses Ergebnis lässt sich nur schwer anwenden, da so viele ${\displaystyle m}$ geprüft werden müssen. Im Jahr 1891 verbesserte Lucas den Satz und erhielt den nach ihm benannten Primzahltest:

(Lucas-Test) Eine natürliche Zahl ${\displaystyle n}$ ist genau dann eine Primzahl, wenn es ein ${\displaystyle a}$ mit ${\displaystyle 1<a<n}$ gibt, für das

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

sowie

${\displaystyle a^{m}\not \equiv 1{\pmod {n}}}$

für alle echten Teiler ${\displaystyle m<n-1}$ von ${\displaystyle n-1}$ gilt.[1]

Da hier nur noch die Teiler von ${\displaystyle n-1}$ getestet werden müssen, sind erheblich weniger Rechenschritte nötig. Ein Nachteil ist jedoch, dass man die Primfaktorzerlegung von ${\displaystyle n-1}$ kennen muss. ${\displaystyle n-1}$ muss also faktorisiert werden. Für Zahlen mit einem besonderen Aufbau ist diese Methode aber sehr effizient, so zum Beispiel bei Zahlen der Form ${\displaystyle 2^{k}+1}$.

Ist die Bedingung des Lucas-Tests für eine Basis ${\displaystyle a}$ nicht erfüllt, so folgt nicht, dass die Zahl ${\displaystyle n}$ zusammengesetzt ist. Dafür müsste man nämlich alle Basen ${\displaystyle 1<a<n}$ prüfen.

Beispiel:

Für die Zahl ${\displaystyle n=59}$ gilt ${\displaystyle 2^{58}\equiv 1\ mod\ 59}$. Die echten Teiler von ${\displaystyle n-1=58}$ sind ${\displaystyle 1,2}$ und ${\displaystyle 29}$. Weiter gilt ${\displaystyle 2^{1}\equiv 2\ mod\ 59,2^{2}\equiv 4\ mod\ 59}$ und ${\displaystyle 2^{29}\equiv -1\ mod\ 59}$. Es folgt, dass ${\displaystyle 59}$ eine Primzahl ist.

Erweiterungen von Lehmer, Brillhart und Selfridge

Derrick Henry Lehmer f​and 1953 d​en verbesserten Lucas-Test. Im Jahr 1967 w​urde eine weitere Version (flexibler Lucas-Test) v​on John Brillhart u​nd John L. Selfridge entdeckt.

Verbesserter Lucas-Test

Der verbesserte Lucas-Test beruht auf folgender Eigenschaft:
${\displaystyle n}$ ist genau dann eine Primzahl, wenn es eine natürliche Zahl ${\displaystyle a}$ mit ${\displaystyle 1<a<n}$ gibt, für die

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

sowie

${\displaystyle a^{\frac {n-1}{q_{i}}}\not \equiv 1{\pmod {n}}}$

für alle Primfaktoren ${\displaystyle q_{i}}$ von ${\displaystyle n-1}$ gilt.

Die Anwendung dieses Tests a​uf Fermat-Zahlen w​ird mit Pépin-Test bezeichnet.

Flexibler Lucas-Test

Der flexible Lucas-Test beruht auf folgender Eigenschaft:
Für die natürliche Zahl ${\displaystyle n}$ sei die Primfaktorzerlegung von ${\displaystyle n-1}$ gegeben durch

${\displaystyle n-1=q_{1}^{e_{1}}\cdot \ldots \cdot q_{r}^{e_{r}}}$.

Dann gilt: ${\displaystyle n}$ ist genau dann eine Primzahl, wenn es zu jedem Primfaktor ${\displaystyle q_{i}}$ eine natürliche Zahl ${\displaystyle a_{i}}$ mit ${\displaystyle 1<a_{i}<n}$ gibt, für die

${\displaystyle a_{i}^{n-1}\equiv 1{\pmod {n}}}$

sowie

${\displaystyle a_{i}^{\frac {n-1}{q_{i}}}\not \equiv 1{\pmod {n}}}$

gilt.[2]

Beispiel

Wir betrachten die Primzahl ${\displaystyle n=911}$. Die Vorgängerzahl ${\displaystyle n-1=910}$ hat die Primteiler ${\displaystyle q=2,5,7}$ und ${\displaystyle 13}$. Die folgende Tabelle zeigt dazu passende ${\displaystyle a}$ und wie die Bedingungen erfüllt werden:

q	a	a^n-1 ≡ 1 (mod n)	a^(n-1)/q ≢ 1 (mod n)
2	7	7^910 ≡ 1 (mod 911)	7^910/2 ≡ -1 (mod 911)
5	3	3^910 ≡ 1 (mod 911)	3^910/5 ≡ 482 (mod 911)
7	2	2^910 ≡ 1 (mod 911)	2^910/7 ≡ 568 (mod 911)
13	2	2^910 ≡ 1 (mod 911)	2^910/13 ≡ 577 (mod 911)

Pratt Primzahltest[3][4]

Der Pratt-Test ist ein iterierter Lucas-Test. Für alle Primfaktoren von ${\displaystyle n-1}$ wird wiederum geprüft, ob diese Primzahlen sind.

Fermat-Paar

${\displaystyle (a,b)}$ ist ein Fermat-Paar, falls ${\displaystyle (a,b)=(1,2)\lor (a\geq 2\land a^{n-1}\not \equiv 1\mod n)}$

Pratt-Sequenz

${\displaystyle (a_{1},b_{1})\dots (a_{k},b_{k})}$ ist eine Pratt-Sequenz, wenn für jedes Fermat-Paar ${\displaystyle (a,b)}$ aus der Sequenz gilt, dass für jeden Primfaktor ${\displaystyle p}$ von ${\displaystyle b}$ ein Fermat-Paar ${\displaystyle (a',p)}$in der Prattsequenz enthalten ist und es gilt: ${\displaystyle a^{\frac {n-1}{p}}\not \equiv 1}$

Für jede Primzahl gibt es eine Pratt-Sequenz in der Länge der Darstellung der Primzahl, weshalb ${\displaystyle Prime\in NP}$.

Beispiel

Für ${\displaystyle 797}$ ist folgendes eine Mögliche Pratt-Sequenz

${\displaystyle (5,797),(1,2),(6,199),(5,3),(3,11)}$

zu Überprüfen ist nun noch, ob ${\displaystyle a^{b-1}\equiv 1}$ und danach, ob für die Primteiler ${\displaystyle p}$ von ${\displaystyle b-1}$ gilt, ${\displaystyle a^{\frac {b-1}{2}}\not \equiv }$

${\displaystyle (5,797)}$

${\displaystyle 5^{797-1}\mod 797\equiv 5^{796}\mod 797\equiv 1}$

${\displaystyle 5^{\frac {796}{2}}\mod 797\equiv 5^{398}\mod 797\equiv 796\not \equiv 1}$

${\displaystyle 5^{\frac {796}{199}}\mod 797\equiv 5^{4}\mod 797\equiv 625\not \equiv 1}$

${\displaystyle (6,199)}$

${\displaystyle 6^{199-1}\mod 199\equiv 6^{198}\mod 199\equiv 1}$

${\displaystyle 6^{\frac {198}{2}}\mod 199\equiv 6^{99}\mod 199\equiv 198\not \equiv 1}$

${\displaystyle 6^{\frac {198}{3}}\mod 199\equiv 6^{66}\mod 199\equiv 192\not \equiv 1}$

${\displaystyle 6^{\frac {198}{11}}\mod 199\equiv 6^{18}\mod 199\equiv 63\not \equiv 1}$

${\displaystyle (5,3)}$

${\displaystyle 5^{3-1}\mod 3\equiv 5^{2}\mod 3\equiv 1}$

${\displaystyle 5^{\frac {2}{2}}\mod 3\equiv 5^{1}\mod 3\equiv 2\not \equiv 1}$

${\displaystyle (2,5)}$

${\displaystyle 2^{5-1}\mod 5\equiv 2^{4}\mod 5\equiv 1}$

${\displaystyle 2^{\frac {2}{2}}\mod 5\equiv 2^{1}\mod 5\equiv 2\not \equiv 1}$

Literatur

• Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin u. a. 2006, ISBN 3-540-34283-4 (Springer-Lehrbuch).
• John Brillhart, D. H. Lehmer, J. L. Selfridge: New Primality Criteria and factorizations of ${\displaystyle 2^{n}\pm 1}$. In: Mathematics of Computation. 29, 1975, ISSN 0025-5718, S. 620–647, online (PDF; 2,14 MB).

Einzelnachweise

1. Beweise hierzu: siehe Ribenboim, Die Welt der Primzahlen, Seite 40.
2. Zum Beweis dieses und des vorigen Satzes siehe Ribenboim, Die Welt der Primzahlen, Seite 42.
3. Daniela Steidl: Primzahlzertifikat von Pratt. 17. April 2008, abgerufen am 7. Mai 2020.
4. apl. Prof. Dr. Klaus Reinhardt: Pratt Primzahlentest. Abgerufen am 7. Mai 2020 (deutsch, englisch).