Cryptography Reference
In-Depth Information
fellos wäre es besser, einen nichtprobabilistischen Algorithmus für den Primzahl-
test zu verwenden. Alle hierzu bekannten Methoden sind jedoch so aufwendig,
dass ein probabilistisches Verfahren allemal die deutlich bessere Wahl ist.
Das mit Abstand bedeutendste Verfahren zur Primzahlgenerierung ist das
Miller-Rabin-Verfahren
. Dieses ist leicht zu implementieren und funktioniert
nach dem oben beschriebenen Prinzip. Miller-Rabin sieht vor, dass zuerst eine
Zufallszahl generiert wird, um anschließend mit einem sehr effektiven probabilis-
tischen Test zu überprüfen, ob es sich um eine Primzahl handelt. Falls nicht, wird
die nächste Zufallszahl auf diese Weise getestet. Dabei kommt für jeden Test eine
zusätzliche Zufallszahl zum Einsatz, die kleiner als die getestete sein muss. Da der
Primzahltest probabilistisch ist, besteht die (geringe) Gefahr, dass eine Zufalls-
zahl den Test besteht, obwohl sie nicht prim ist. Viele Implementierungen führen
deshalb mehrere Testrunden mit unterschiedlichen zusätzlichen Zufallszahlen
durch. Die Wahrscheinlichkeit, dass eine Nichtprimzahl alle Runden übersteht,
wird dadurch verschwindend gering. Wie das Miller-Rabin-Verfahren genau
funktioniert, können Sie unter anderem in den Standardwerken [Schn96] und
[MeOoVa] nachlesen.
In der Praxis wird Miller-Rabin meist mit einigen einfachen Vorabmaßnah-
men kombiniert. So werden das erste und das letzte Bit einer zu testenden Zahl
auf Eins gesetzt, damit die Zahl groß genug und ungerade ist. Außerdem wird
vorab auf direktem Weg getestet, ob die betrachtete Zahl durch kleinere Primzah-
len (beispielsweise alle Primzahlen kleiner als 2.000) teilbar ist. Erst wenn diese
Vortests positiv verlaufen sind, wird das Miller-Rabin-Verfahren angewendet.
