![[JoGu]](../../JOGUUNM1-opti.gif) |
KryptologieIII.5 Harte zahlentheoretische Probleme |
|
|
KryptologieIII.5 Harte zahlentheoretische Probleme |
|
Einleitung [als PDF-Datei].
... und das Ganze am Stück als PDF-Datei.
Die folgende Tabelle gibt einen Überblick über kryptologisch relevante zahlentheoretische Berechnungsprobleme. »Effizient« bedeutet dabei »mit polynomialem Aufwand lösbar«.
| Berechnungsproblem | effizient? | behandelt in |
|---|---|---|
| Primzahltest | ja | 3.1 - 3.8 |
| [für Primzahl p] | ||
| Finde primitives Element Finde quadratischen Nichtrest Quadratrest-Eigenschaft Quadratwurzel ziehen Diskreter Logarithmus |
ja (ERH oder prob.) ja (ERH oder prob.) ja ja (ERH oder prob.) ? (vermutlich nein) |
A.2, A.10 A.9 A.6 folgt in 5.3 4.1, 4.6 |
| [für zusammengesetzte Zahl n] | ||
| Faktorisierung RSA-Inversion (e-te Wurzel) Berechnung der EULER-Funktion Berechnung der CARMICHAEL-F. Finde primitives Element Quadratrest-Eigenschaft Quadratwurzel ziehen Diskreter Logarithmus |
? (vermutlich nein) ? (vermutlich nein) ? (vermutlich nein) ? (vermutlich nein) ? (vermutlich nein) ? (vermutlich nein) ? (vermutlich nein) ? (vermutlich nein) |
2.2, 2.4 2.2 2.2 2.2 A.4 A.8 folgt in 5.5 folgt in 5.1 |
»ERH« bedeutet »unter Annahme der erweiterten RIEMANNschen Vermutung«, »prob.« bedeutet »mit einem probabilistischen Algorithmus«.
Der Zusammenhang zwischen den Berechnungsproblemen für eine zusammengesetzte Zahl n wird in der folgenden Grafik dargestellt. Ein Pfeil von A nach B bedeutet dabei, dass das Problem B mit einem effizienten probabilistischen Algorithmus auf das Problem A reduzierbar ist. Die Umkehrungen bei den einfachen Pfeilen sind jeweils unbekannt. Die Reduktionen, die durch rote Pfeile bezeichnet sind, werden im folgenden bewiesen. (Z. T. nur für den Fall, dass n Produkt zweier Primzahlen ist.)
![[Reduktionen]](Redukt.gif)