Wahrscheinlichkeit für eine Primzahl

Question

dass ist die Aufgabe.

Du suchst eine neue Lieblingszahl,die gleichzeitig auch eine Primzahl ist.  Du besitzt einen Algorithmus, der testet ob es eine Primzahl ist. Dieser Algorithmus ist randomisiert: Für eine Primzahl liefert er stets die Ausgabe "wahrscheinlich Primzahl"; ist die Eingabezahl jedoch zusammengesetzt, liefert der Algorithmus nur mit Wahrscheinlichkeit 75% die Ausgabe "sicher zusammengesetzt" (und mit der restlichen Wahrscheinlichkeit trotzdem die Ausgabe "wahrscheinlich Primzahl"). Die Wahrscheinlichkeit hängt dabei nicht von der Eingabe ab, sondern von einem unabhängigen Zufallsexperiment. Du hast bereits einen Kandidaten K als deine Lieblingszahl im Auge. Du möchtest erreichen,dass wenn K zusammengesetzt ist, dies auch mit einer Wahrscheinlichkeit von mindestens 1 − 2⁻⁶⁴ herausfinden.

Wie gehst du vor ?

Meine Überlegung:

Also ich bin nicht so fit mit Wahrscheinlichkeiten, aber ich dachte man sucht solange 0,75^sqrt(K) die gewünschte Wahrscheinlichkeit erreicht. Aber wie ich das erreichen kann, weiß ich leider nicht. Und wäre es dann nicht doch von der Eingabelänge abhängig?

Answer 1

Ich löse die Gleichung

1 - (1 - 0.75)^n ≥ 1 - 2^(-64) --> n ≥ 32

Und weiß das ich so 32 unabhängige Versuchsexperimente machen müßte.

Comments

Danke für die Antwort:) aber ich versteh jetzt nicht ganz warum du 1 - (1 - 0.75)ⁿ ≥ machst ?

---

mit 0.75 wird erkannt das K zusammengesetzt ist.

mit 1 - 0.75 wird nicht erkannt das K zusammengesetzt ist.

mit (1 - 0.75)^n wird n mal nicht erkannt das K zusammengesetzt ist.

mit 1 - (1 - 0.75)^n wird mindestens einmal erkannt das K zusammengesetzt ist.

Und diese Wahrscheinlichkeit soll größergleich einem gegebenen Wert sein.