Erweiterter euklidischer Algorithmus

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Beitragvon Goswin » Donnerstag 7. Mai 2009, 10:25

:D my cody isch nosch mehr sexxi: :D

Code: Alles auswählen

def extended_euclid(a, b):
  #liefert (ggt, mul_a, mul_b) mit ggt==mul_a*a+mul_b*b

  if b==0:
    print( "\nggT = %(a)d" %vars() )
    print( "Linearkombination des ggT aus Ausgangszahlen:\n" )
    #
    return (a, 1, 0) #a==1*a+0*b
   
  else:
    (faktor, rest) = divmod(a,b)  #a==faktor*b+rest
    print( "%(a)4d  = %(faktor)4d * %(b)4d   +  %(rest)4d"%vars() )
    #
    (ggt, inn_mul_a, inn_mul_b) = extended_euclid(b, rest)  #innere mul
    (mul_a, mul_b) = (inn_mul_b, inn_mul_a-faktor*inn_mul_b)
    print("%(ggt)4d  =  (%(mul_a)4d) * %(a)4d  +  (%(mul_b)4d) * %(b)4d"%vars())
    #
    return (ggt, mul_a, mul_b) #ggt==mul_a*a+mul_b*b


(a,b) = (374, 230)
extended_euclid(a, b)
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon Dill » Donnerstag 7. Mai 2009, 10:34

mehr rundungen hat deiner auf jeden fall :shock:
ich steh aber auf weniger üppig.
in meiner neuen version verschwinden jetzt die hilfsberechnungen in print() und trüben so nicht den blick auf den eigentlichen algo :)
(und: ich bleibe bei den namen aus der wikipedia wo ich den algo herhabe)

Code: Alles auswählen

def extended_euclid(a, b):
    if b == 0:
        print('\nggT: %d\nggT:= Linearkombination(Ausgangszahlen):\n' % a)

        return a, 1, 0

    else:
        print('%(a)d = %(faktor)d * %(b)d +  %(a_mod_b)d'
           % dict({"faktor":a/b, "a_mod_b":a%b}, **locals())
        )
       
        d_, s_, t_ = extended_euclid(b, a % b)
        d, s, t = d_, t_, s_ - (a/b) * t_
       
        print('%(d)d = %(s)d * %(a)d + %(t)d * %(b)d' % locals())
       
        return d, s, t
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Donnerstag 7. Mai 2009, 19:39

Hi Leute^^

Also erst mal danke für die Verbesserungsvorschläge und Dill, versteh mich nicht falsch aber ich glaub ich verstehe den Algo von Goswin etwas besser :wink:

Also Danke ich hab das jetzt auch ein bisschen schöner gemacht, so dass es jetzt so aussieht:

Code: Alles auswählen

a = 9013
b = 1556
g = a
h = b
c = a%b
modul = []     
vielfach = [] 
rest = []
multi = []
while c > 0:
    print ("%d = %d * %d + %d" % (g, g//h, h, c))
    modul.append(g)
    vielfach.append(h)
    multi.append(g//h)
    rest.append(c)
    g = h
    h = c
    c = g%h
    if g%h == 0:
        break
   
print ("--------------------------------------------------------------------")

rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()

i = 0
while len(rest) > i:
        print ("%d = %d * %d + %d" % (rest[i], modul[i], multi[i], vielfach[i]))
        i = i + 1

print ("--------------------------------------------------------------------")


g = a
h = b

def extgcd(a, b):
    c=b
    u=1
    s=0
    while b>0:
        q=a//b
        a, b = b, a-q*b
        u, s = s, u-q*s
    if u < 0:
        u = u + c
    return u

d = extgcd(h, g)

print ("d = ", extgcd(h, g))
print ("b = ", b)
print ("a = ", a)
print ("(d * b) % a = ", (d*b)%a)


und vielen Dank yipyip, jetzt hab ich endlich mal verstanden, was du die ganze Zeit mit Wikipedia gemeint hast.. ich hab das gar nicht gesehen, dass die das so da berechnet haben!

Also es funktioniert jetzt endlich :)
und es sieht hoffentlich nicht mehr alzu "unschön" :wink: aus

Liebe Grüße
Kalira
Benutzeravatar
Goswin
User
Beiträge: 361
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen

Beitragvon Goswin » Freitag 8. Mai 2009, 15:14

Aha, BAHNHOF!


@Kalira: Deine Aufgabestellung (was dein extgcd(a,b) ausgibt) ist offenbar NICHT, was andere Leute unter dem "Erweiterten Euklidschen Algorithmus" verstehen, sie geht wohl mehr in Richtung eines "Mysteriösen Kaliraschen Algorithmus".

Ich denke, die Forumsteilnehmer haben nach all diesem Aufwand schon ein Recht auf eine mathematische Beschreibung von was GENAU du die ganze Zeit über gesucht hast; dazu brauchst du ja kein Python, nur Deutsch und Mathe. Du wolltest lineare Ausdrücke in andere lineare Ausdrücke einsetzen, aber MIT WELCHEM ZIEL? Nur Python lernen war es wohl auch nicht auch nicht so ganz.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 8. Mai 2009, 16:01

Meine Euclid()-Implementation liefert für

Code: Alles auswählen

e = Euclid(9013, 1556)
print e.steps
print e.extended


diese Ausgabe:

Code: Alles auswählen

9013 = 5·1556+1233
1556 = 1·1233+323
1233 = 3·323+264
 323 = 1·264+59
 264 = 4·59+28
  59 = 2·28+3
  28 = 9·3+1
   3 = 3·1+0

1 = 1·28-9·3
  = 1·28-9·(59-2·28) = 19·28-9·59
  = 19·(264-4·59)-9·59 = 19·264-85·59
  = 19·264-85·(323-1·264) = 104·264-85·323
  = 104·(1233-3·323)-85·323 = 104·1233-397·323
  = 104·1233-397·(1556-1·1233) = 501·1233-397·1556
  = 501·(9013-5·1556)-397·1556 = 501·9013-2902·1556


Da weiß man wenigstens, was man hat ...
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Beitragvon Kalira » Samstag 9. Mai 2009, 10:04

:lol:

ok, sorry wenn ich euch ein bisschen verwirrt habe :wink:

Also bei einer RSA-Verschlüsselung verwendet man den erweitertern euklidischen Algorithmus um den geheimen Schlüssel d zu berechnen.
Sprich ich habe einen öffentlichen Schlüssel e und mein Modul der Verschlüsselung N.
Das Modul N ist das Produkt von 2 Primzahlen. Jetzt lässt sich dadurch ganz einfach die Anzahl der Zahlen bestimmen, die kleiner sind als N und teilerfremd zu dieser sind. Diese Anzahl wird mit der eulerischen-phi-Funktion φ(n) beschrieben und es gilt φ(n) = φ(p*q) = (p-1)*(q-1)
(Allerdings müssen q und p jeweils Primzahlen sein)

Jetzt berechnet sich der geheime Schlüssel d mit Hilfe des erweiterten euklidischen Algorithmus bezüglich e und φ(n)...

das heißt im Endeffekt soll einfach nur gelten, dass d*e mod φ(n) = 1 ist, somit brauche ich die 2te Zahle des erweiterten euklidischen Algorithmus gar nicht...

Und die Verschlüsselung selbst erfolgt einfach so, dass ich meinen Klartext K habe diesen mit e potenziere und eine Division mit Rest bezüglich N mache. Also:

K^e mod N = C wobei C der Geheimtext ist

und um den Geheimtext wieder zu entschlüsseln berechnet man:

C^d mod N = K

So und deshalb brauche ich nur die eine Zahl :wink:

Liebe Grüße
Kalira

PS: Wenn ihr auch gerne noch wissen wollte, warum die Verschlüsselung so funktioniert, dann sagt bescheid, aber das wird dann schon etwas spezieller und mathematischer :wink:

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]