Miller-Rabin-Test

19.02.2007, 17:04	ajax2leet	Auf diesen Beitrag antworten »
Miller-Rabin-Test Nabend, ich habe ein wenig Probleme, das Prinzip des Miller-Rabin-Primzahltests zu verstehen. Beim googlen habe ich zwar verschiedene Beweise gefunden, allerdings waren die alle ziemlich Knapp gehalten. Ich wäre sehr dankbar, wenn sich jemand bemüht, mir diesen Test so einfach wie möglich zu erklären.
19.02.2007, 18:43	Tobias	Auf diesen Beitrag antworten »
Also Miller-Rabin soll prüfen, ob eine gegebene ungerade Zahl n zusammengesetzt ist. Dafür stellt man n mit maximalem k so dar: $\begin{eqnarray} n = q\cdot 2^k + 1 \end{eqnarray}$ D.h. in n-1 ist $\begin{eqnarray} 2^k \end{eqnarray}$ der größte gerade Teiler und q ist ungerade. Du ziehst nun zufällig und gleichverteilt ein $\begin{eqnarray} a \in \mathbb{Z}_n^\ast. \end{eqnarray}$ . a und n haben also keine gemeinsamen Teiler bis auf die 1. Nun erzeugst du nacheinander folgende Quadrate: $\begin{eqnarray} a^q, a^{2q}, a^{2^2q}, \ldots, a^{2^{k-1}q} \end{eqnarray}$ a ist ein Zeuge dafür, dass n zusammengesetzt ist, wenn für alle i gilt $\begin{eqnarray} a^{2^iq} \not\equiv -1 \end{eqnarray}$ und zusätzlich $\begin{eqnarray} a^q \not\equiv 1 \end{eqnarray}$ . Jetzt kann man zeigen, dass es für n prim keine solchen Zeugen gibt. Angenommen n wäre prim und es gäbe einen Zeugen a, für den das obere gilt. Aus dem kleinen Satz von Fermat folgt: $\begin{eqnarray} a^{n-1} = a^{2^kq} \equiv 1 \end{eqnarray}$ Nun ist aber $\begin{eqnarray} a^{2^kq} \end{eqnarray}$ das Quadrat von $\begin{eqnarray} a^{2^{k-1}q} \end{eqnarray}$ . Da $\begin{eqnarray} \mathbb{Z}_n \end{eqnarray}$ im Fall n prim ein Körper ist, hat $\begin{eqnarray} a^{2^kq} \end{eqnarray}$ nur die Wurzeln 1 und -1. Die Wurzel -1 ist aber verboten nach unserer Annahme, dass a ein Zeuge ist. Es bleibt nur die 1. Dieses System pflanzt sich bis nach $\begin{eqnarray} a^q \end{eqnarray}$ fort, so dass am Ende $\begin{eqnarray} a^q \end{eqnarray}$ kongruent zu 1 oder -1 sein müsste. Das ist aber nach Annahme ebenfalls verboten. Also gibt es keinen solchen Zeugen a.
19.02.2007, 21:49	ajax2leet	Auf diesen Beitrag antworten »
Alles klar, habs verstanden Danke!
20.02.2007, 16:54	ajax2leet	Auf diesen Beitrag antworten »
Ich habe jetzt eine kleine Herleitung für den Test geschrieben. Es wäre nett, wenn jmd. vielelicht mal einen Blick darauf werfen könnte und mir sagen könnte, ob es an irgendwelchen Stellen Fehler oder unklarheiten gibt. An einigen Stellen gibt es noch Verweise auf Artikel, die ich jetzt aber der Einfachheit halber rausgelassen habe. Danke im Vorraus! btw. das ganze ist für eine Facharbeit Klasse 12 Gymnasium ----------------------------------------------- Der Miller-Rabin ist eine Weiterentwicklung des fermatischen Primzahltests. Er macht sich zusätzlich zum kleinen Fermatschen Satz die Eigenschaft zu nutze, dass eine quadratische Lösung in einem Zahlenkörper nur zwei Nullstellen hat. Einen solchen Körper stellt $\begin{eqnarray} \mathbb{Z}_p \end{eqnarray}$ dar, welcher die Menge der Restklassen, die bei einer Division durch p entstehen, bezeichnet. Ist p keine Primzahl, kann $\begin{eqnarray} \mathbb{Z}_p \end{eqnarray}$ auch kein Körper sein, weshalb dann quadratische Gleichungen in $\begin{eqnarray} \mathbb{Z}_p \end{eqnarray}$ mehr als 2 Lösungen haben können (aber nicht müssen!). Betrachten wir nun noch einmal den kleinen Fermatschen Satz: $\begin{eqnarray} a^{n-1} \equiv 1 \mod n \end{eqnarray}$ Für ungerade n gilt dann: $\begin{eqnarray} n-1 = 2^pq \\ a^{2^pq} \equiv 1 \mod n \end{eqnarray}$ Nun stellen wir $\begin{eqnarray} a^{2^pq} \end{eqnarray}$ als Quadratzahl dar: $\begin{eqnarray} x^2 \equiv 1 \mod n \\ x^2-1 \equiv 0 \mod n \\ n \Bigm \| x^2-1 \\ n \Bigm \| (x+1)(x-1) \end{eqnarray}$ D.h. $\begin{eqnarray} x \end{eqnarray}$ kann nur die Lösungen 1 und -1 haben. Mehr als 2 Lösungen können unter der Annahme, dass $\begin{eqnarray} n \end{eqnarray}$ prim ist, nicht existieren (s.o.) $\begin{eqnarray} n \Bigm \| \sqrt{a^{2^pq}}+1 \quad \vee \quad n \Bigm \| \sqrt{a^{2^pq}} -1 \\ \sqrt{a^{2^pq}} \equiv -1 \mod n\quad \vee \quad \sqrt{a^{2^pq}} \equiv 1 \mod n \\ \sqrt{a^{2^pq}} = a^{2^{p-1}q} \\ \end{eqnarray}$ Betrachten wir die Reste der Division durch p ergibt sich: $\begin{eqnarray} a^{2^{p-1}q} \mod n = 1 \quad \vee \quad a^{2^{p-1}q} \mod n = -1 \end{eqnarray}$ Das der Rest einer Division -1 sein soll, mag etwas ungewohnt sein, heißt aber nichts anderes als $\begin{eqnarray} a^{2^{p-1}q} \mod n = -1 \Leftrightarrow a^{2^{p-1}q} \mod n = p-1 \end{eqnarray}$ Ziehen wir nun immer weiter die Wurzel, gelangen wir schließlich zu: $\begin{eqnarray} a^q \equiv 1 \mod n \quad \vee \quad a^q \equiv -1 \mod n \end{eqnarray}$ Nun sollen diese Aussagen zu einem Primzahlentest kombiniert werden. Betrachten wir nocheinmal die Aussagen (11) und (13). Der Satz von Fermat kann nur dann gültig sein, wenn $\begin{eqnarray} a^{2^iq} \end{eqnarray}$ einmal kongruent zu -1 war (Die nachfolgenden Quadrate demnach $\begin{eqnarray} (-1)^2 = 1 \end{eqnarray}$ ) oder aber die letzte Wurzel $\begin{eqnarray} a^q \end{eqnarray}$ bereits 1 war. Finden wir ein $\begin{eqnarray} a \end{eqnarray}$ , so dass $\begin{eqnarray} a^{2^iq} \not\equiv -1 \end{eqnarray}$ für alle $\begin{eqnarray} i \end{eqnarray}$ mit $\begin{eqnarray} 0\le i\le p-1 \end{eqnarray}$ und $\begin{eqnarray} a^q \not\equiv 1 \end{eqnarray}$ gilt, ist $\begin{eqnarray} n \end{eqnarray}$ als zusammengesetzt identifiziert. Leider gibt es auch bei diesem Test das Problem, dass ihn Zahlen, die nicht prim sind, überstehen sind. Solche Zahlen nennt man in diesem Fall starke Pseudoprimzahlen. Für ein zufällig gewähltes $\begin{eqnarray} a \end{eqnarray}$ beträgt die Fehlerwahrscheinlichkeit bei k-maligem Ausführen des Tests mit zufällig generierten $\begin{eqnarray} a \end{eqnarray}$ $\begin{eqnarray} 0.25^k % \end{eqnarray*}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »