Probabilistischer Algorithmus für Primzahltests

30.11.2012, 17:41	GlasgowKid	Auf diesen Beitrag antworten »
Probabilistischer Algorithmus für Primzahltests Meine Frage: Zusätzlich zu dem in der Vorlesung vorgestellten Monte-Carlo-Algorithmus $\begin{eqnarray} A \end{eqnarray}$ für die Primzahlen gebe es einen probabilistischen Algorithmus $\begin{eqnarray} B \end{eqnarray}$ mit polynomieller Laufzeit $\begin{eqnarray} T_B \end{eqnarray}$ , der Primzahlen mit Wahrscheinlichkeit $\begin{eqnarray} 1-\epsilon_B \end{eqnarray}$ korrekt erkennt für ein $\begin{eqnarray} \epsilon_B>0 \end{eqnarray}$ und bei einer Nichtprimzahl immer mit "nichtprim" terminiert. Konstruieren Sie daraus einen effizienten Algorithmus für die Sprache PRIMES, der als Antwort die Werte "prim","nichtprim" oder "?" geben kann, wobei "?" mit Wahrscheinlichkeit höchstens 0,1 auftreten darf. Meine Ideen: Ich weiß, daß beide Algorithmen A und B einen einseitigen Fehler haben und damit auch als stochastische Tests verstanden werden können. Test A gibt mir immer, wenn x eine Primzahl ist, auch als Ergebnis "wahr" zurück, aber wenn x keine Primzahl ist, kann man "wahr" oder "falsch" erhalten mit Fehlerwahrscheinlichkeit (Fehler 1. Art) von max. 1/4. Test B liefert mir falls x keine Primzahl ist immer das richtige Ergebnis "falsch", falls x aber eine Primzahl ist, tritt das falsche Ergebnis "wahr" mit Fehlerwahrscheinlichkeit (Fehler 2. Art) $\begin{eqnarray} \epsilon_B \end{eqnarray}$ auf. Mein Vorgehen ist ungefähr so: Ich führe Test A aus, wenn ich "wahr" erhalte ist alles klar, ich kann terminieren mit Ausgabe "prim". Wenn ich "falsch" erhalte kann x eine Primzahl sein oder auch nicht, also führe ich zur Sicherheit Test B aus. Liefert der "falsch" zurück ist alles klar und ich kann terminieren mit Ausgabe "nichtprim", liefert der aber auch wahr zurück ist meine Ausgabe "?", weil ich immer noch keine sichere Antwort habe. Die Frage ist: Wie oft muß ich denn mit "?" antworten? Also wie oft habe ich das Ergebnis "A ist wahr und B ist falsch"? Oder besser: Wie groß ist die Wahrscheinlichkeit das A "wahr" und gleichzeitig B "falsch" ist? Durch mehrmaliges Ausführen von A kann ich die Wahrscheinlichkeit für die Ausgabe von "?" minimieren, denn P("?"\|A(x)=wahr)>P("?"\|2 mal A(x)=wahr) (genauso wie beim Würfeln die Wahrscheinlichkeit zweimal eine Sechs zu würfeln, eben nicht mehr 1/6 sondern 1/36 ist). Ich habe jetzt drei Ereignisse definiert: $\begin{eqnarray} A= \end{eqnarray}$ Algorithmus $\begin{eqnarray} A(x) \end{eqnarray}$ terminiert mit Ausgabe "wahr". $\begin{eqnarray} B= \end{eqnarray}$ Algorithmus $\begin{eqnarray} B(x) \end{eqnarray}$ terminiert mit Ausgabe "wahr". $\begin{eqnarray} C= x \in \text{PRIMES} \end{eqnarray}$ d.h. x ist eine Primzahl Und dann folgende bedingte Wahrscheinlichkeiten aufgestellt: $\begin{eqnarray} P(A\|C)=1 \Rightarrow P(\neg A\|C)=0 \end{eqnarray}$ $\begin{eqnarray} P(B\|\neg C)=0 \Leftarrow P(\neg B\|\neg C)=1 \end{eqnarray}$ $\begin{eqnarray} P(C\|\neg A)=0 \Leftarrow P(\neg C\|\neg A)=1 \end{eqnarray}$ $\begin{eqnarray} P(C\|B)=1 \Rightarrow P(\neg C\|B)=0 \end{eqnarray}$ $\begin{eqnarray} P(A\|\neg C)=\epsilon_A \le 1/4 \Rightarrow P(\neg A\|\neg C)=1-\epsilon_A \ge 3/4 \end{eqnarray}$ $\begin{eqnarray} P(B\|C)=1-\epsilon_B \Rightarrow P(\neg B\|C)=\epsilon_B \end{eqnarray}$ $\begin{eqnarray} P(C\|A)=\frac{P(C)}{P(A)} \Rightarrow P(\neg C\|A)=\frac{P(A)-P(C)}{P(A)} \end{eqnarray}$ $\begin{eqnarray} P(C\|\neg B)=\frac{P(\neg B)-P(\neg C)}{P(\neg C)} \Leftarrow P(\neg C\|\neg B)=P(\neg C)/P(\neg B) \end{eqnarray}$ Gesucht ist die Wahrscheinlichkeit $\begin{eqnarray} P("?")=P(A \cap \neg B) \end{eqnarray}$ Beziehungsweise soll durch mehrmaliges ausführen von A (und B) gelten $\begin{eqnarray} P("?")=P(A^m \cap \neg B^n) \le 0.1 \end{eqnarray}$ und eine entsprechende Belegung für $\begin{eqnarray} n, m \end{eqnarray}$ gefunden werden. Hier komme ich nicht weiter, denn entweder lande ich durch Umformungen in einer Sackgasse (Tautologie) oder mir fehlen Elementarwahrscheinlichkeiten für P(A), P(B) oder P(C).

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »