Ausgangslage

Die erzeugte Zahl ´n´ ist ungerade und hat als 500-Bit-Zahl einen Wert im Bereich bis etwa ´2^500´. Da das letzte Bit fest auf 1 gesetzt ist und die übrigen 499 Bits zufällig (gleichverteilt) sind, ist ´n´ im Wesentlichen eine zufällig gleichverteilte ungerade Zahl in ´{1, 3, 5, …, 2^500 - 1}´.

Anzahl der Kandidaten

Im Intervall bis ´N := 2^500´ gibt es genau ´N/2 = 2^499´ ungerade Zahlen. Das ist die Menge, aus der der Zufallsgenerator gleichverteilt zieht.

Anzahl der Primzahlen

Nach dem Primzahlsatz gilt

´π(N) ≈ N / ln(N)´.

Bis auf die einzige gerade Primzahl 2 (die wir vernachlässigen) sind alle Primzahlen ungerade. Die Anzahl der ungeraden Primzahlen bis ´N´ ist also ebenfalls näherungsweise ´N / ln(N)´.

Wahrscheinlichkeit

Da gleichverteilt aus den ungeraden Zahlen gezogen wird, ist

´p ≈ ("Anzahl ungerader Primzahlen" ≤ N) / ("Anzahl ungerader Zahlen" ≤ N) = (N / ln(N)) / (N / 2) = 2 / ln(N)´.

Der Faktor 2 ist genau der Gewinn dadurch, dass von vornherein nur ungerade Zahlen betrachtet werden: Verglichen mit einer Ziehung aus allen Zahlen (Trefferwahrscheinlichkeit ´1 / ln(N)´) verdoppelt sich die Chance.

Einsetzen der Zahlen

Mit ´N = 2^500´ ist

´ln(N) = 500 · ln(2) ≈ 500 · 0,6931 ≈ 346,6´.

Damit

´p ≈ 2 / 346,6 ≈ 0,00577 ≈ 0,58 %´.

Das entspricht etwa einer Trefferchance von 1 zu 173.

Bemerkung zur Interpretation

Der Primzahlsatz liefert eine asymptotische Dichte; bei einer konkreten Zahl der Größe ´2^500´ ist die Näherung sehr gut. In der Praxis (z. B. RSA-Schlüsselerzeugung) bedeutet das: Man muss im Mittel etwa 173 ungerade Zahlen mit einem Primzahltest prüfen, bis man eine Primzahl findet — eine durchaus praktikable Größenordnung.