2.3 Große Primzahlen
Beispielsweise für RSA benötigt man große, d.h. mind. 80-stellige Primzahlen.
Üblicherweise erzeugt man zufällige große Zahlen und testet sie dann mit einem Monte Carlo-Algorithmus wie z.B. Solovay-Strassen oder Miller-Rabin auf Primalität. Diese Algorithmen sind schnell (polynomiell zur Länge der Zahl in Binärdarstellung), können aber behaupten, daß n prim ist, auch wenn es nicht prim ist. Indem man den Algorithmus oft genug anwendet, kann die Fehlerquote unter jede beliebige Schranke gedrückt werden.
Die andere Frage ist, wieviele Zufallszahlen (gegebener Größe) man testen muß, bis man eine Primzahl findet. Ein berühmtes Ergebnis der Zahlentheorie besagt, daß die Anzahl der Primzahlen kleiner als N ungefähr N / ln N beträgt.
Wenn man also p zufällig wählt, ist die Wahrscheinlichkeit, daß es prim ist, 1 / ln p. Für einen 512 Bit langen Modulus heißt das 1 / ln p = 1/177 (oder 2/177, wenn man sich gleich auf ungerade Zahlen beschränkt).
Ein yes-biased Monte Carlo-Algorithmus ist ein probabilistischer Algorithmus für ein Entscheidungsproblem, wobei eine "Ja"-Antwort immer stimmt, eine "Nein"-Antwort aber falsch sein kann. Ein no-biased Monte Carlo-Algorithmus ist entsprechend definiert.
Ein yes-biased Monte Carlo-Algorithmus hat Fehlerwahrscheinlichkeit EPSILON, wenn er für jede Instanz, für die die Antwort "Ja" lautet, die (falsche) Antwort "Nein" mit Wahrscheinlichkeit von höchstens EPSILON gibt.
