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?