0 Daumen
612 Aufrufe

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−64 herausfinden.

Wie gehst du vor ?

Meine Überlegung:

Also ich bin nicht so fit mit Wahrscheinlichkeiten, aber ich dachte man sucht solange 0,75sqrt(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?

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

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.

Avatar von 487 k 🚀

Danke für die Antwort:) aber ich versteh jetzt nicht ganz warum du 1 - (1 - 0.75)n ≥ 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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community