Pohlig-Hellman

Neue Frage »

HelpSera Auf diesen Beitrag antworten »
Pohlig-Hellman
Hi,
ich versuche gerade den Algo "Pohlig-Hellman" zu verstehen mit dem sich der diskrete logarithmus berechnen läßt.
Hier mal ein Beispiel:
www-math.cudenver.edu/~wcherowi/courses/m5410/phexam.html

In jedem der Teilschritte sind mir 2 Sachen nicht klar. Nehmen wir z.b. die Berechnung von x_2

Determination of x_2.
Since x_2 is a number mod 4, we have x_2 = c_0 + c_1*2, with the coefficients being either 0 or 1. We determine these coefficients as follows.

7531^((p-1)/2) = 7531^4050 = -1 and as this = a^(c0 (p-1)/2), we have c0 = 1.
Now, divide 7531 by a^c_0 to get
7531(a^-1) = 7531(6751) = 8006 mod p.
8006(p-1)/4 = 80062025 = 1 and as this = a^(c1 (p-1)/2), we have c_1 = 0.

x_2 = c_0 + c_1 (2) = 1 + 0(2) = 1.


Die Stellen die ich nicht verstehe sind hervorgehoben.

Wieso folgt aus 7531^4050 = -1 dass c0 = 1 ??

und wieso ist 7531(a^-1) = 7531 * 6751 = 8006 mod p ??
Reksilat Auf diesen Beitrag antworten »
RE: Pohlig-Hellman
Hallo,

Du vergisst a=6:

Zitat:
Wieso folgt aus 7531^4050 = -1 dass c0 = 1?

Es ist
Und insofern muss ungerade sein.

Zitat:
und wieso ist 7531(a^-1) = 7531 * 6751 = 8006 mod p?

Es ist

Gruß,
Reksilat.
sonett Auf diesen Beitrag antworten »

Da hätte ich jetzt auch mal eine Frage dazu. Ich glaube ich stehe da gerade auf den Schlauch: Es ist ja nach c0 gefragt worden und du schreibst jetzt a^x^(p-1)/2 dahin.
Sollte es nicht a^c0^(p-1)/2 lauten? In welcher Beziehung stehen x und c0 zueinander? Also, welchen Sinn macht dieses aufteilen des gesammten x ?

Danke schonmal für die Antworten. smile
Reksilat Auf diesen Beitrag antworten »

Hi sonett,

Sorry für die späte Antwort, hatte Dienstag keine Zeit mehr und habe es dann vergessen.

Es sei .
.

Wir wissen, dass ist. Außerdem ist (beides mit Fermat).
Wir können nun ausrechnen und erhalten .
Wäre nun gerade, so wäre Ein Widerspruch.

Damit ist ungerade.

Die sind jetzt einfach nur Bezeichner, um herauszuarbeiten, welchen Wert modulo 4, 81 und 25 hat. Damit wird dann am Ende per chinesischem Restsatz errechnet.
Hier sind und gerade die Werte aus , die erfüllen. Ist ungerade, so muss sein.

Gruß,
Reksilat.
sonett Auf diesen Beitrag antworten »

Ja super! danke! Habs jetzt endlich kapiert. smile smile smile
So leuchtet das ein...
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »