Kryptologie Die multiplikative Gruppe Primitive Elemente und Quadratreste

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

In diesem mathematischen Einschub werden einige mathematische Probleme geschlossen behandelt, die in der Kryptologie eine Rolle spielen und die multiplikative Gruppe eines Restklassenrings betreffen. Z. B. beruhen die Sicherheitsaussagen für manche kryptographische Verfahren auf der Nichtexistenz effizienter Algorithmen für einige dieser Probleme.

Der eigentliche mathematische Inhalt steht als Extrakapitel »Primitive Elemente und Quadratreste« als PDF-Datei zur Verfügung.

Die hier behandelten Probleme und ihre (nur z. T. behandelten) Lösungen sind:

1. Finden eines primitiven Elements.
   • Die Komplexität ist im allgemeinen Fall unbekannt.
   • Die vollständige Suche ist aber effizient, falls die erweiterte RIEMANNsche Vermutung [*] richtig ist.
   • Es gibt einen sehr effizienten probabilistischen Algorithmus, der aber im schlechtesten Fall nicht einmal terminiert.
   • Für viele Primzahlen ist die Lösung trivial.
   • Der Nachweis der Primitivität ist effizient, wenn die Primfaktoren der Ordnung der multiplikativen Gruppe bekannt sind; sonst ist die Komplexität unbekannt.
   • Der Fall eines zusammengesetzten Moduls ist auf den seiner Primfaktoren reduzierbar, falls diese bekannt sind.
2. Erkennen von Quadratresten.
   • Für Primzahlmoduln gibt es einen effizienten Algorithmus.
   • Der Fall eines zusammengesetzten Moduls ist auf den der Primfaktoren reduzierbar, falls diese bekannt sind.
   • Für zusammengesetzte Moduln ist die Komplexität unbekannt; vermutlich ist das Problem hart (so hart wie die Primzerlegung).
3. Finden eines quadratischen Nichtrests.
   • Die Komplexität ist im allgemeinen Fall unbekannt.
   • Die vollständige Suche ist aber effizient, falls die erweiterte RIEMANNsche Vermutung richtig ist.
   • Es gibt einen sehr effizienten probabilistischen Algorithmus, der aber im schlechtesten Fall nicht einmal terminiert.
   • Für die meisten Primzahlen ist die Lösung trivial.
   • Der Fall eines zusammengesetzten Moduls ist auf den seiner Primfaktoren reduzierbar, falls diese bekannt sind.

[*] über die Martin HUXLEY in einem Limerick sagt:

Tell the Riemann Hypothesis crew
That zeta alone will not do.
Precise applications
to nice situations
Require it for L-functions too.