Wie kann ich ein Modulo umkehren?
Ich habe die werte p=29 g=7 m=24 n=23
m=7^a mod 29 n=7^b mod 29
Ich möchte a bzw b bestimmen. Mein Plan wäre eine umkehr operation anzuwenden von Modulo um 7^a bzw 7^b zu bestimmen und dann log7 anwenden um a bzw b bestimmen. Wäre das eine Möglichkeit oder soll ich einen anderen Lösungsweg verwenden Alle Vorschläge sind herzlich angenommen
4 Antworten
Hey,
das Problem an der Modulorechnung ist, sie ist nicht injektiv und damit nicht eindeutig umkehrbar.
Injektivität bedeutet ja, für alle x1, x2 mit f(x1)=f(x2) folgt x1=x2, Da Mod nicht injektiv, existieren mindestens zwei x1 und x2 mit f(x1)=f(x2) und x1 != x2 (ungleich). Bzgl. der Modulorechnung rechnest du ja mit Restklassen, die bzgl. einer Äquivalenzrelation entstehen (man identifiziert alle Zahlen miteinander, die nach der Division mit dem Mod, den gleichen Rest haben.) Aus den Restklassen wählst du idR den kleinsten Repräsentanten und nutzt dieses stellvertretend. Insgesamt rechnest du aber mit Mengen.
Wenn du 7^a mod X und 7^b mod X kennst, kannst du zwar 7^{ab} mod X konstruieren, aber nicht a und b (außerhalb eines Bruteforces) herleiten. Dieses Problem ist auch als Discrete Logarithm Problem bekannt. (DLP) Suche danach, dann findest du einige Lösungsansätze.
Btw. mod 29 kannst du noch gut per Hand rechnen.. da 7 und 29 coprim sind, ist 7 ein Erzeuger. Weiter weißt du, dass 7^{28} = 1 mod 29. Bleiben also nur (!) 25 Potenzen zu testen. (0 und 1 können vernachlässigt werden.)
Nun kannst du entweder per Bruteforce vorgehen: 7^2, 7^3, ... 7^{27} und jeweils mod 29 reduzieren, oder du erkennst zwischendurch ein paar gute Tricks ;) In Übungsaufgaben dieser Art wird von euch verlangt, die Modulorechnung für Potenzierungen zu wiederholen und um weiteres Wissen zu ergänzen.
Eine Umkehrabbildung von modulo gibt es nicht (nicht-injektive Funktion). Wäre schön - dann könnten wir die Methoden der αναλυσις (das böse, böse A-Wort, griechisch für "Auflösung") auch auf Körper von Primzahlgrad anwenden.
Logarithmen in Restklassenkörpern und ihren Erweiterungen sind etwas haariger als im Körper der rationalen Zahlen und seinen Erweiterungen.
Immerhin gelten die üblichen Potenzgesetze auch in Restklassenkörpern für ganzzahlige Exponenten.
Es gibt einen Satz von Lagrange ( https://de.wikipedia.org/wiki/Satz_von_Lagrange ), der - auf die multiplikative Gruppe des Körpers angewendet - besagt, dass für alle x ∈ K \ {0} gilt: x^(|K|-1) = 1
Kannst du das auf deine Aufgabe anwenden?
Das ist das Problem des diskreten Logarithmus, für das es in den meisten Gruppen, so auch in der primen Restklassengruppe, im allgemeinen kein effizientes Lösungsverfahren gibt. Darauf beruhen viele puplic Key Kryptosysteme
Gar nicht, deshalb findet man den Modulo auch in Algorithmen zur Erzeugung von Pseudozufallszahlen.