Pohlig-Hellman |
22.02.2009, 17:37 | HelpSera | Auf diesen Beitrag antworten » | ||||
Pohlig-Hellman 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 ?? |
||||||
23.02.2009, 01:04 | Reksilat | Auf diesen Beitrag antworten » | ||||
RE: Pohlig-Hellman Hallo, Du vergisst a=6:
Es ist Und insofern muss ungerade sein.
Es ist Gruß, Reksilat. |
||||||
31.03.2009, 19:16 | 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. |
||||||
02.04.2009, 23:03 | 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. |
||||||
06.04.2009, 10:53 | sonett | Auf diesen Beitrag antworten » | ||||
Ja super! danke! Habs jetzt endlich kapiert. So leuchtet das ein... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |