[JoGu]

Kryptologie

III.3 Primzahltests

a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

  1. Der Pseudoprimzahltest [PDF-Datei].
  2. Der strenge Pseudoprimzahltest [PDF-Datei].
  3. Der Primzahltest von MILLER [PDF-Datei].
  4. Die erweiterte RIEMANNSCHE Vermutung [PDF-Datei].
  5. Der probabilistische Primzahltest von RABIN [PDF-Datei].
  6. RSA und Pseudoprimzahlen [PDF-Datei].
  7. Der polynomielle Primzahltest von AGRAWAL-KAYAL-SAXENA [PDF-Datei].
  8. Der AKS-Algorithmus [PDF-Datei].

Das Ganze gibt's auch am Stück als PDF-Datei.


Eine Frage ist zur Durchführbarkeit des RSA-Verfahrens noch zu klären: Gibt es überhaupt Möglichkeiten, die für die Schlüsselerzeugung nötigen Primzahlen zu finden? Die Antwort wird lauten: Ja, das ist effizient möglich. Man startet mit einer zufälligen Zahl der benötigten Bitlänge und prüft, ob sie eine Primzahl ist. Falls nein, prüft man die nächstgrößere Zahl usw., bis man eine Primzahl gefunden hat.

Nötig sind also Verfahren, die effizient entscheiden, ob eine natürliche Zahl prim ist - sogenannte Primzahltests.

Hierbei tritt ein Phänomen auf, das man auch von anderen mathematischen Problemen (z. B. lineare Optimierung, Bestimmung von Polynomnullstellen) kennt:

Bei den Primzahltests ist der neu entdeckte AKS-Algorithmus polynomial, kann aber mit dem etablierten RABIN-Algorithmus nicht mithalten, der sehr effizient ist, aber im schlechtesten Fall nicht einmal das richtige Ergebnis liefert.

Da alle genannten Primzahltests einen beachtlichen Overhead haben, wird man in der praktischen Anwendung stets zuvor die Teilbarkeit durch »kleine« Primzahlen prüfen, etwa durch Primzahlen < 106, je nach verfügbarem Speicherplatz: Man legt nämlich dazu eine Liste L dieser Primzahlen an.

Benötigt man nun eine zufällig gewählte Primzahl einer bestimmten Größe, so wählt man zufällig eine Zahl r in diesem Größenbereich - sollte r gerade sein, erhöht man um 1. Dann siebt man nach dem ERATOSTHENES-Verfahren das Intervall [r, r+s] nach den Vielfachen der Primzahlen in L aus; damit die Chance, noch etwas übrig zu behalten, hinreichend groß ist, sollte man s als deutlich größer als die größte Zahl in der Liste L wählen. Die Zahlen, die übrig bleiben, werden der Reihe nach dem gewünschten Primzahltest unterzogen, bis man eine gefunden hat, die den Test besteht. In den allermeisten Fällen wird das bereits die erste sein.


Autor: Klaus Pommerening, 28. Mai 2000; letzte Änderung: 7. August 2014.