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: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

: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

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
http://www.kinderpornos.info
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

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: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

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

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

: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:
Antworten