Wahrscheinlichkeit, dass eine erzeugte Zahl prim ist

Wir erzeugen ungerade Zahlen mit 500 Bits, wobei das höchste Bit (Position 499) eine führende Null sein darf. Die erzeugten Zahlen liegen also im Bereich

´0 <= z < 2^500´, wobei ´z´ ungerade ist.

Es gibt genau ´2^499´ ungerade Zahlen in diesem Bereich (jede Wahl der 499 freien Bits liefert genau eine ungerade Zahl), und jede tritt mit gleicher Wahrscheinlichkeit auf.

Anzahl der Primzahlen unter diesen Kandidaten: Alle Primzahlen außer ´2´ sind ungerade. Nach dem Primzahlsatz gilt

´pi(n) ~~ n/ln(n)´.

Mit ´n = 2^500´:

´pi(2^500) ~~ (2^500)/(ln(2^500)) = (2^500)/(500 * ln 2)´.

Bis auf die vernachlässigbare ´2´ sind alle diese Primzahlen ungerade und damit mögliche Kandidaten.

Wahrscheinlichkeit ´p´ für „prim":

´p = "Anzahl Primzahlen"/"Anzahl ungerader Kandidaten" = (2^500//(500 ln 2))/(2^499) = 2/(500 * ln 2)´.

Numerisch:

´p = 2/(500 * 0,6931...) = 2/(346,57...) ~~ 0,005771´.

Anzahl der nötigen Versuche

Bei ´k´ unabhängigen Versuchen ist die Wahrscheinlichkeit, keine Primzahl zu erhalten, gleich ´(1-p)^k´. Gefordert ist

´1 - (1-p)^k >= 0,99 hArr (1-p)^k <= 0,01´.

Logarithmieren (beachte: ´ln(1-p) < 0´, daher dreht sich die Ungleichung):

´k >= (ln(0,01))/(ln(1-p))´.

Einsetzen mit ´p ~~ 0,005771´, also ´ln(1-p) ~~ ln(0,994229) ~~ -0,005788´:

´k >= (-4,6052)/(-0,005788) ~~ 795,6´.

Anmerkung: Eine bequeme Näherung erhält man auch über ´(1-p)^k ~~ e^(-pk)´. Aus ´e^(-pk) <= 0,01´ folgt ´k >= (ln 100)/p = 4,6052/0,005771 ~~ 798´ — praktisch dasselbe Ergebnis in der gleichen Größenordnung.