#1 17. Februar 2010 Hey, kann mir einer den Erweiterter euklidischer Algorithmus anhand des folgenden Beispiels erklären? 7*d=1 (mod160) danke im voraus.
#2 17. Februar 2010 AW: Erweiterter euklidischer Algorithmus Also ich konnte es damals hier gut nachvollziehen: http://www.johannes-bauer.com/thi/eea.php Stehe aber auch grad wieder aufm Schlauch.
#3 17. Februar 2010 AW: Erweiterter euklidischer Algorithmus 1.) 160 div 7 = 22, 160 mod 7 = 6 => 160 = 22*7 + 6 => 6 = 160*1 +7*(-22) 2.) 7 div 6 = 1 , 7 mod 6 = 1 => 7 = 1*6 + 1 => 1 = 7 -6*1 => 1 = 1*7 -(160*1 +7(-22))=23*7 +(-1)*160 3.) 6 div 1 = 6 , 6 mod 1 = 0 => ggt(160,7)= 1 mit Koeffizienten a=23 b=-1 1=23*7 + (-1)*160 7*23 = 161 = 1 mod 160
#4 17. Februar 2010 AW: Erweiterter euklidischer Algorithmus Tut mir leid, aber iwie versteh ich überhaupt garnichts...
#5 17. Februar 2010 AW: Erweiterter euklidischer Algorithmus der euklidische algorithmus ist folgendermaßen rekursiv definiert: EUCLID(a,b) 1 wenn b = 0 2 dann return a 3 sonst return EUCLID(b, a mod b) auf dein beispiel ggt(160,7): - 160 mod 7 = 6 => ggt(7,6) - 7 mod 6 = 1 => ggt(6,1) - 6 mod 1 = 0 => ggt(1,0) - ggt(160,7) = 1 ich hoffe das erklärt es besser. damit hast du aber nur den ggt gefunden, aber nicht die koeffizienten. deshalb hab ich oben den aktuellen wert bei a mod b durch vielfache von 160 und 7 dargestellt. z.B. : bei ersten unterstrich 160 mod 7 = 6 . Wir wissen nun 160 lässt sich als 160 = 22*7 + 6 schreiben, wobei 6 der rest bei einer ganzzahligen division ist. daraus folgt für 6 = 160 +(-22)*7. das mache ich für die nachfolgenden modulowerte auch. 7 mod 6 = 1 . damit lässt sich 7 = 1*6 +1 darstellen. wir wollen nu wieder den rest 1 durch 7 und 160 darstellen. => 1 = 7 -1*6 . Setzt man nun den oberen wert für 6 ein ( 6 = 160 +(-22)*7) ergibt sich für die eins folgender wert : 1 = 7-(160 +(-22)*7) = 23*7 -1*160. damit hast du die koeffizientendarstellung für den ggt von 160 un 7 . damit ist dein d aus 7*d=1 (mod160) nun d = 23 . den 7*23= 161. 161 mod 160 = 1 . wenn das immer noch nicht verständlich, frag genau, was du nciht verstehst.