Benutzer:Abrankov/Vorlesung/Lucas-Test

Lucas-Test

Primzahltests auf Grundlage von Kongruenzen

Édouard Lucas

Satz (Lucas Test)

Eine natürliche Zahl ${}n$ ist genau dann eine Primzahl, wenn es eine

natürliche Zahl ${}0<a<n$ gibt mit

${}a^{n-1}\equiv 1\mod n,\,\,\,{\text{ aber }}\,\,\,a^{\frac {n-1}{q}}\not \equiv 1\mod n\,$

für alle Primteiler ${}q$ von ${}n-1$.

Beweis

Benutzer:Abrankov/Lucas Test/Fakt/Beweis

$\Box$

Beispiel

Wir wollen zeigen, dass ${}n=61$ prim ist. Wegen ${}n-1=60=2^{2}\cdot 3\cdot 5$ folgt dies aus

${}2^{\frac {60}{2}}=2^{30}=(2^{6})^{5}=64^{5}\equiv 3^{5}\equiv 60\not \equiv 1\mod 61$,

${}2^{\frac {60}{3}}=2^{20}=(2^{6})^{3}\cdot 2^{2}={64}^{3}\cdot 2^{2}\equiv 3^{3}\cdot 4\equiv 47\not \equiv 1\mod 61$,

${}2^{\frac {60}{5}}=2^{12}=(2^{6})^{2}=64^{2}\equiv 3^{2}\equiv 9\not \equiv 1\mod 61$.

Eine direkte Verallgemeinerung des Lucas Test ist der Pocklington Test:

Satz (Pocklington)

Sei ${}n$ eine natürliche Zahl, so dass ${}n-1$ eine Faktorisierung der Form ${}n-1=RF$ besitzt, wobei alle Primteiler von ${}F$ bekannt sind. Weiterhin gebe es eine natürliche Zahl ${}0<a<n$ mit

1. ${}a^{n-1}\equiv 1\mod n$
2. ${}{ggT}\,(a^{\frac {n-1}{q}}-1,n)=1$

für alle Primteiler ${}q$ von ${}F$. Ist dann ${}F\geq {\sqrt {n}}$, so ist ${}n$ eine Primzahl.

Beweis

Benutzer:Abrankov/Pocklington Test/Fakt/Beweis

$\Box$

Die anderen berühmten Primzahlen sind die Fermatschen Primzahlen, obwohl man davon nur 5 Stück kennt und vermutet, dass es keine weiteren gibt. Auch für diese Zahlen gibt es einen speziellen Test, den Pepin Test. Er beruht auf dem Lucas Test, der immer anwendbar ist, wenn man die Primteiler von ${}n-1$ kennt. Für die Fermatschen Primzahlen reicht es aus, im Lucas Test die Zahl ${}a=3$ zu überprüfen:

Satz (Pepin Test)

Die Zahl

${}F_{r}=2^{2^{r}}+1{,}\,\,\ r\geq 1$, ist genau dann eine Primzahl, falls

${}3^{\frac {F_{r}-1}{2}}\equiv -1\mod F_{k}\,.$

Beweis

Benutzer:Abrankov/Pepin Test/Beweis

$\Box$

Beispiel

Da ${}F_{r}$ doppelt exponentiell in ${}r$ wächst, kann man den Test per Hand nur für sehr kleine ${}r$ durchführen. Wir betrachten hier ${}F_{2}=2^{2^{2}}+1=2^{4}+1=17$. Diese Zahl ist prim, weil

${}3^{\frac {F_{2}-1}{2}}=3^{2^{3}}=3^{8}=(3^{4})^{2}\equiv 13^{2}\equiv -1\mod 17\,.$

Bei der Anwendung des Lucas Tests auf eine beliebige Zahl ${}n\in \mathbb {N}$ gibt es zwei Probleme:

1. Man muss die Primteiler von ${}n-1$ kennen. Dies ist ein Faktorisierungsproblem und damit im Allgemeinen schwierig.
2. Man muss alle ${}n-1$ Werte für ${}a$ überprüfen. Dies bedeutet einen sehr hohen Rechenaufwand. (Die Anzahl könnte man verkleinern, wenn man berücksichtigt, dass es ${}\varphi (n-1)$ Primitivwurzeln modulo ${}n$ für ${}n$ prim gibt. Man bleibt aber in der gleichen Größenordnung für den Rechenaufwand.)

Um das erste Problem in den Griff zu bekommen, könnte man hoffen, dass ein ${}n\in \mathbb {N}$ bereits prim ist, falls ${}a^{n-1}\equiv 1\mod n$ ist für alle zu ${}n$ teilerfremden ${}a$ im Bereich von ${}1$ bis ${}n-1$. Das ist aber leider nicht richtig.

Satz (Miller-Rabin Test)

Sei ${}n\geq 3$ ungerade und ${}n-1=2^{t}m{\text{ für }}m$ ungerade. ${}n$ ist genau dann eine Primzahl, wenn für jede zu ${}n$ teilerfremde Zahl ${}0<a<n$ gilt

${}a^{m}\equiv 1\mod n\,\,\,{\text{ oder }}\,\,\,2^{s}m\equiv -1\mod n{\text{ für }}{\text{ ein }}s\in \{0,1,\ldots ,t-1\}\,.$

Ist ${}n$ keine Primzahl, so erfüllt höchstens ein Viertel alle Zahlen ${}a$ eine der Bedingungen.

Beispiel

Wir möchten überprüfen, ob 89 mit Miller-Rabin Test eine Primzahl ist. Es gilt ${}n-1=88=2^{3}\cdot 11$, also ${}t=3$. Wir testen für zwei zufällige Zahlen ${}a=3$ und ${}a=5$ erhalten wir:

${}3^{11}\equiv 37\mod n$

${}3^{2.11}\equiv 37^{2}\equiv 34\mod n$

${}3^{4.11}\equiv 37^{2}\equiv -1\mod n$

${}5^{11}\equiv 55\mod n$

${}5^{2.11}\equiv 55^{2}\equiv -1\mod n$

Die zwei Testzahlen erfüllen die Testbedingung.

Lucas-Folgen

................... ...................

Primzahltests auf Grundlage von Lucas-Folgen

Der Lucas-Lehmer-Test ist ein Verfahren, um Mersenne-Primzahlen zu überprüfen. Entwickelt wurde der Test von Eduardo Luca und Derrick Henry Lehmer, der die Arbeiten von Luca fortsetzte. Als mathematische Grundlagen dienen Lucas-Folgen. Häufigste Verwendung findet der Test beim Suchen von sehr großen Primzahlen. Er ist seit Jahren die effizienteste Methode, um die größten zurzeit bekannten Primzahlen zu entdecken, und wird als Standardtestverfahren beim GIMPS-Projekt (Great Internet Mersenne Prime Search) eingesetzt. Zuerst werden wir der Lucas-Lehmer-Test für beliebige Zahl n zeigen und dann für Mersenne-Primzahlen.

Lemma

Sei ${}{ggT}(Q,n)=1$. Es existiert ein ${}d\geq 1$, sodaß die Menge ${}G=\{t\mid U_{t}\equiv 0\mod n\}$ und ${}G$ hat die Form ${}G=d\cdot \mathbb {N}$.

Beweis

Benutzer:Abrankov/Lucas-Lehmer-Test/Lemma/Fakt/Beweis

$\Box$

Satz (Lucas-Lehmer-Test)

Sei ${}n+1=\prod _{j=1}^{r}{q_{j}}^{\beta _{j}}$ mit ${}q_{j}$ paarweise verschiedenen Primzahlen. Sei ${}U_{i}$ eine Lucas-Folge mit ${}\operatorname {ggT} \,(2QcD,n)=1$ und

${}\operatorname {ggT} \,(U_{\frac {n-1}{q_{j}}},n)=1\,\,\,{\text{ für alle }}j=1,2,...,r\,.$

Ist nun ${}U_{n+1}\equiv 0\mod n$,

so ist ${}n$ prim.

Beweis

Benutzer:Abrankov/Lucas-Lehmer-Test/Beweis

$\Box$

Lucas-Lehmer-Test für Mersennezahlen

............................ ............................

Literatur

• [B] Brenner H.: Zahlentheorie (Osnabrück 2008) http://de.wikiversity.org/wiki/Zahlentheorie_(Osnabr%C3%BCck_2008)(13.03.09)
• Burton, D.M./Dalkowski, H.: Handbuch der elementaren Zahlentheorie.Neldermann Verlag, 2005, ISBN 3-88538-112-5
• Müller-Stach,S./Piontkowski, J.: Elementare und algebraische Zahlentheorie.1. Auflage Wiesbaden : Vieweg, 2006, ISBN 978-3-8348-0211-8
• Ribenboim, P.: Die Welt der Primzahlen: Geheimnisse und Rekorde, Springer-Verlag Berlin Heidelberg, 2006 ISBN 978-3-540-34284-7
• Riesel,H.: Prime Numbers and Computer Methods for Factorization. Birkhäuser, ISBN 0-8176-3291-3