Pohlig-Hellman

Dieses Thema im Forum "Schule, Studium, Ausbildung" wurde erstellt von Hanskopf, 22. Februar 2009 .

  1. 22. Februar 2009
    Hi,
    hier sind doch bestimmt einige Studenten unterwegs

    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 ??
     
  2. 23. Februar 2009
    AW: Pohlig-Hellman

    Ich kann dir leider keinen konstruktiveren Tipp geben, als dich mit deinem Problem an eines der zahlreichen Matheforen im Netz zu wenden.

    Dein Problem geht ja nun schon in die angewandte Mathematik und du wirst hier nur schwer Hilfe finden, da bietet sich ein Matheforum wirklich besser an.

    Entschuldige bitte, aber ich finde, dass es besser ist, dir diesen Tipp zu geben, als gar nichts zu schreiben
     
  3. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.