Zum Inhalt springen

Benutzer:Abrankov/Lucas-Test/latex

Aus Wikiversity






\zwischenueberschrift{Lucas-Test}






\zwischenueberschrift{Primzahltests auf Grundlage von Kongruenzen}


Édouard Lucas





\inputfaktbeweis
{Benutzer:Abrankov/Lucas Test/Fakt}
{Satz}
{Lucas Test}
{Eine natürliche Zahl $n$ ist genau dann eine Primzahl, wenn es eine

natürliche Zahl $0 < a < n$ gibt mit
\mathdisp {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$. }
{Benutzer:Abrankov/Lucas Test/Fakt/Beweis

}





\inputbeispiel{ }
{ Wir wollen zeigen, dass $n = 61$ prim ist. Wegen $n-1=60=2^2\cdot3\cdot5$ folgt dies aus \einrueckung{$2^\frac {60} 2=2^{30}=(2^6)^5 =64^5\equiv 3^5\equiv 60 \not\equiv 1\mod 61$,} \einrueckung{$2^\frac {60} 3=2^{20}=(2^6)^3\cdot2^2 ={64}^3\cdot2^2\equiv 3^3\cdot4\equiv 47 \not\equiv 1\mod 61$,} \einrueckung{$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:





\inputfaktbeweis
{Benutzer:Abrankov/Pocklington Test/Fakt}
{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

\aufzaehlungzwei {$a^{n-1}\equiv1\mod n$ } {${ggT} \,(a^\frac{n-1}q-1,n) =1$ } für alle Primteiler $q$ von $F$. Ist dann $F\ge\sqrt n$, so ist $n$ eine Primzahl. }
{Benutzer:Abrankov/Pocklington Test/Fakt/Beweis

}


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:





\inputfaktbeweis
{Benutzer:Abrankov/Pepin Test}
{Satz}
{Pepin Test}
{Die Zahl

$F_r=2^{2^r}+1{ , } \,\,\ r \ge 1$, ist genau dann eine Primzahl, falls
\mathdisp {3^\frac{F_r-1}2 \equiv -1\mod F_k} {.}
}
{Benutzer:Abrankov/Pepin Test/Beweis

}





\inputbeispiel{}
{ 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


\mathdisp {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:

\aufzaehlungzwei { Man muss die Primteiler von $n-1$ kennen. Dies ist ein Faktorisierungsproblem und damit im Allgemeinen schwierig. } {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.





\inputfakt{Benutzer:Abrankov/Miller-Rabin Test/Fakt}{Satz}{Miller-Rabin Test} {Sei $n\ge3$ ungerade und $n-1=2^tm \text{ für } m$ ungerade. $n$ ist genau dann eine Primzahl, wenn für jede zu $n$ teilerfremde Zahl $0<a<n$ gilt
\mathdisp {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. }




\inputbeispiel{}
{ 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:

\einrueckung{$3^{11} \equiv 37 \mod n$} \einrueckung{$3^{2.11} \equiv 37^2 \equiv 34 \mod n$} \einrueckung{$3^{4.11} \equiv 37^2 \equiv -1 \mod n$}


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


Die zwei Testzahlen erfüllen die Testbedingung.
}







\zwischenueberschrift{Lucas-Folgen} ................... ...................






\zwischenueberschrift{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.





\inputfaktbeweis
{Benutzer:Abrankov/Lucas-Lehmer-Test/Lemma/Fakt}
{Lemma}
{}
{Sei ${ggT}(Q,n)=1$. Es existiert ein $d \ge 1$, sodaß die Menge

$G=\{ t \mid U_t \equiv0\mod n \}$ und $G$ hat die Form $G=d \cdot\mathbb N$. }
{Benutzer:Abrankov/Lucas-Lehmer-Test/Lemma/Fakt/Beweis

}





\inputfaktbeweis
{Benutzer:Abrankov/Lucas-Lehmer-Test}
{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


\mathdisp {\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. }
{Benutzer:Abrankov/Lucas-Lehmer-Test/Beweis

}







\zwischenueberschrift{Lucas-Lehmer-Test für Mersennezahlen}

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

Literatur

Abgerufen von „https://de.wikiversity.org/w/index.php?title=Benutzer:Abrankov/Lucas-Test/latex&oldid=135079“