#1 26. Februar 2010 Zuletzt von einem Moderator bearbeitet: 14. April 2017 Hey, ich muss für meine Facharbeit den erweiterten Euklidischen Algorithmus können, aber ich komme nicht ganz klar damit. Bsp: ggT(99,78 ) Wie die erste und zweite Spalte zustande kommt weiß ich, aber wie kommt die dritte zu stande? Und wie komme ich damit auf die Inverse d? Mein Bsp: ggT(26,11) 26=2*11+4 <-> 4=26-2*11 = ? 11=2*4+3 <-> 3=11-2*4 = ? 4=1*3+1 <-> 1=4-1*3 = ? 3=3*1+0 <-> 0=3-3*1 = ? Danke im voraus.
#3 27. Februar 2010 AW: Erweiterter Euklidischer Algorithmus die dritte kommt durch substitution zustande, wie die zweite. setzt einfach die werte für 21 und 15 aus den ersten beiden zeilen ein. 6 = 1*21 -1*15 = 1*(1*99-1*78 ) - 1*(-3*99 + 4*78 ) = 4*99 - 5*78. Bei der vierten wird dann halt 15 und 6 substituiert aus der 2. und 3. zeile. Ich hoffe das war verständlich. ist dir teil vor dem Äquivalenzzeichen klar ?
#4 28. Februar 2010 AW: Erweiterter Euklidischer Algorithmus Auf dein 2. Beispiel : ggT(26,11) 26=2*11+4 <-> 4=26-2*11 , 4 ist schon als vielfaches von 26 und 11 dargestellt 11=2*4+3 <-> 3=11-2*4 = 11- 2*( 26-2*11 ) = -2*26 + 5*11 --> Wert für 4 aus 1. zeile eingesetzt 4=1*3+1 <-> 1=4-1*3 = ( 26-2*11 ) -1*( -2*26 + 5*11 ) = 3*26 -7*11 --> werte für 4 und 3 aus den ersten beiden zeilen eingesetzt 3=3*1+0 <-> 0=3-3*1 = brauchste nicht umstellen, da 1 = ggT(26,11) = 3*26 -7*11
#5 1. März 2010 AW: Erweiterter Euklidischer Algorithmus Mhh, ich verstehe das immer noch nicht, wie die dritte spalte zustande kommt. Weiß auch nicht wie ich den erweiterten Euklidischen Algorithmus auf den RSA-Algorithmus beziehen soll. Beispiel zu RSA: d=47^-1 mod 5760 = 1103, ich weiß nicht wie das Ergebnis rauskommt. Gruß LuIgI