-
Pohlig-Hellman-Verfahren zur Bestimmung des diskreten Logarithmus
Der diskrete Logarithmus ist die Umkehrfunktion der diskreten Exponentiation und zählt zu den schwierigen Problemen in der Zahlentheorie. Zu gegebenen natürlichen Zahlen a und x und einer Primzahl p lässt sich ax mod p einfach bestimmen. Sind jedoch natürliche Zahlen a, b und eine Primzahl p gegeben, so ist die Gleichung ax mod p= b nur schwer nach x auflösbar. Eine Möglichkeit ist das Pohlig-Hellman-Verfahren.
Die Aufgabe besteht darin, den mathematischen Hintergrund aufzuschreiben, diesen am Rechner umzusetzen und die Berechnungskomplexität nachzuvollziehen.
-
Pohlig-Hellman-Verfahren zur Verschlüsselung von Nachrichten
Auf Basis der Berechnungskomplexität des diskreten Logarithmus gibt es das Pohlig-Hellman-Verschlüsselungsverfahren. Zu gegebenen natürlichen Zahlen a und x und einer Primzahl p lässt sich ax mod p einfach bestimmen. Sind jedoch natürliche Zahlen a, b und eine Primzahl p gegeben, so ist die Gleichung ax mod p= b nur schwer nach x auflösbar. Dies nutzt man aus, um Nachrichten, die durch eine Zahl 0 ≤ M ≤ p kodiert sind, zu verschlüsseln.
Aufgabe ist es, den mathematischen Hintergrund des Verfahrens zur Ver- und Entschlüsselung zu beschreiben und am Rechner umzusetzen. Zudem sollen praktische Schwierigkeiten und Schwächen des Verfahrens aufgezeigt werden.