Was bezüglich dem EEA, wie geht das? |
| 15.03.2006, 16:55 | Bebbo | Auf diesen Beitrag antworten » |
| Was bezüglich dem EEA, wie geht das? 1 = ax + ny Jetzt soll laut einem Buch folgen: 1 = 1 mod n = ax mod n + ny mod n = ax mod n Ich verstehe, dass ax mod n + ny mod n = ax mod n ist, aber wieso darf man einfach den modulo Operator in die Gleichung 1 = ax + ny reinbringen? Woher will man wissen, dass die gleichung: 1 = ax + ny für die modulo-gleichung: 1 mod n = ax mod n + ny mod n noch gilt? |
||
| 15.03.2006, 17:06 | AD | Auf diesen Beitrag antworten » |
Wenn zwei Zahlen gleich sind, dann gehören sie auch in dieselbe Restklasse, egal welches Modul: Z.B. lässt 11 durch 7 geteilt den Rest 4 und nicht zugleich den Rest 3 o.ä. !!! |
||
| 15.03.2006, 17:31 | Bebbo | Auf diesen Beitrag antworten » |
Achso Danke, die Regel kannte ich leider noch gar nicht. Ist das irgendein bekannter Satz? Oder kann man ihn auch herleiten? |
||
| 15.03.2006, 18:00 | AD | Auf diesen Beitrag antworten » |
Der grundlegende "Satz" lautet: Wenn , dann ist für jede beliebige Funktion , denn es wird ja ein- und dasselbe Argument genommen, also muss auch ein- und derselbe Funktionswert rauskommen!!! Und das hat primär nichts mit Zahlentheorie zu tun... Hier ist z.B. Ich weiß nicht, wie ich es noch primitiver erklären soll. 
|
||
| 15.03.2006, 20:40 | Bebbo | Auf diesen Beitrag antworten » |
Du hast recht! Jetzt hab auch ich das endgültig verstanden! Vielen Dank an dich! |
||
| 16.03.2006, 13:21 | Bebbo | Auf diesen Beitrag antworten » |
Hallo, ich bins nochmal. Ich hab da nochmal ne Frage: ich bin grade dran für den erweiterten euklidischen Algorithmus eine verallgemeinerte Form zu konstruieren. Da das aus meinen Quellen nicht ganz genau hervorgeht, wollte ich nochmal fragen: Um den erweiterten Euklidischen Algorithmus durchzuführen, muss man dazu vorher den Euklidischen Algorithmus durchgeführt haben, damit man dann weißt, wo man eigendlich "hin" möchte... Stimmt das? |
||
| Anzeige | ||
|
|
||
| 16.03.2006, 13:26 | AD | Auf diesen Beitrag antworten » |
Nö, muss man nicht. Es ist dann eben nur so, dass du für gegebene dann Faktoren mit der Eigenschaft ermittelst, ohne dass du am Anfang bereits den Wert kennst - der fällt eben erst zum Schluß an, gemeinsam mit . |
||
| 16.03.2006, 13:51 | Bebbo | Auf diesen Beitrag antworten » |
Hm... dann hab ich wohl irgendetwas übersehen oder falsch verstanden. Ich gebe dir mal ein Beispiel: Ich wende zuerst den erweiterten euklidischen Algorithmus an den Zahlen 26 und 5 an(zur ermittlung des ggT's): (1) 26 = 3 * 7 + 5 (2) 7 = 1 * 5 + 2 (3) 5 = 2 * 2 + 1 (4) 2 = 2 * 1 So, jetzt stelle ich nach dem Rest 1, der der ggT ist in Gleichung 3 um und wende den erweiterten euklidischen Algorithmus an: 1 = 5 - 2*2 1 = 5 - 2*(7 - 1*5) = 5 - 2*7 + 2*1*5 1 = -2*7 + 5*3 1 = -2*7 + (26 - 3*7) * 3 = -2*7 + 26*3 - 7*9 1 = -11*7 + 3*26 Nun habe ich -11 und 3 als Inverse gefunden. An dieser Stelle kann ich nicht nachvollziehen, wie ich ausgehend von den Zahlen 26 und 5 ebenfalls durch den erweiterten Euklidischen Algorithmus auf -11 und 3 komme, ohne dabei wie oben den Euklidischen Algorithmus auszulassen. Wie funktioniert das dann? |
||
| 16.03.2006, 14:14 | AD | Auf diesen Beitrag antworten » |
Alles eine Frage der richtigen Organisation: Wenn du den EEA so durchführst, wie in der Wikipedia beschrieben, dann weißt du, was ich in meinem letzten Beitrag gemeint habe. |
||
| 16.03.2006, 17:29 | Bebbo | Auf diesen Beitrag antworten » |
Tut mir Leid, aber ich habe mich schon mit dem Wikipedia-Artikel beschäftigt und selbst beim nochmaligen lesen, finde ich keinen Bezug zu dem oben beschriebenem Weg an dem Beispiel.... Wie sähe das denn bei dem obigen Beispiel mit 26 und 5 schrittweise aus? |
||
| 16.03.2006, 17:46 | AD | Auf diesen Beitrag antworten » |
Bei Übernahme des Wikipedia-Variablennamen : 26 = 1 * 26 + 0 * 5 5 = 0 * 26 + 1 * 5 ; q = [26/5] = 5 1 = (1-5*0) * 26 + (0-5*1) * 5 = 1 * 26 + (-5) * 5 ; q = [5/1] = 5 0 = (0-5*1) * 26 + (1-5*(-5)) * 5 = (-5) * 26 + 26 * 5 Bei 0 ist Schluß; die vorletzte Zeile enthält dann die gesuchten Informationen: 1.) ggT(26,5) = 1 2.) 1 = 1 * 26 - 5 * 5 EDIT: Ich sehe gerade, du redest laufend von 26 und 5, rechnest aber mit 26 und 7 !!! **grmmml** Also auch das noch: 26 = 1 * 26 + 0 * 7 7 = 0 * 26 + 1 * 7 ; q = [26/7] = 3 5 = (1-3*0) * 26 + (0-3*1) * 7 = 1 * 26 + (-3) * 7 ; q = [7/5] = 1 2 = (0-1*1) * 26 + (1-1*(-3)) * 7 = (-1) * 26 + 4 * 7 ; q = [5/2] = 2 1 = (1-2*(-1)) * 26 + ((-3)-2*4) * 7 = 3 * 26 + (-11) * 7 ; q = [2/1] = 2 0 = ((-1)-2*3)) * 26 + (4-2*(-11)) * 7 = (-7) * 26 + 26 * 7 Ergebnis: ggT(26,7) = 1 = 3 * 26 - 11 * 7 |
||
| 16.03.2006, 18:20 | Bebbo | Auf diesen Beitrag antworten » |
Ersteinmal vielen Dank für deine Geduld und deine Hilfsbereitschaft! Wie kann es mir gelingen, aus der allgemeinen Vorschrift für den Euklidischen Algorithmus, den erweiterten Euklidischen Algorithmus, herzuleiten? ... Wenn ich für den Euklidischen Algorithmus festlege: Schritt 1) a = q*b + r Wobei: r = a mod b q = (a - (a mod b)) / b Schritt 2) Wenn r = 0, dann ist b der größte gemeinsame Teiler. Wenn r = 0, dann setze a = b, b = r, und wiederhole Schritt 1 Dabei enteht nun folgende Abfolge: a_0 = q_0*b_0 + r_0 a_1 = q_1*b_1 + r_1 a_2 = q_2*b_2 + r_2 ... Wobei gilt: a_n = b_n-1 b_n = r_n-1 Aber irgendwie kann ich aus diesen Aussagen nicht den erweiterten Euklidischen Algorithmus herleiten... |
||
| 16.03.2006, 18:45 | AD | Auf diesen Beitrag antworten » |
Wie man das q bestimmt, ist dir klar - einfach Ganzahlanteil der Division von vorletzten durch letzten Gleichungswert, hast du ja gerade beschrieben. Und dann entsteht beim EEA die neue Gleichung, indem man das q-fache der letzten Gleichung von der vorletzten Gleichung abzieht!!! m = s * 26 + t * 7 n = u * 26 + v * 7 ; q = [m/n] ------------------- Jetzt diese Subtraktion: (m-q*n) = (s-q*u) * 26 + (t-q*v) Das ist auch schon alles! Die linke Seite ist das, was du vom einfachen EA kennst, jetzt musst du nur noch die rechte Seite parallel mit durchziehen. |
||
| 17.03.2006, 21:39 | Bebbo | Auf diesen Beitrag antworten » |
Geschafft! Nach sehr viel Hilfe von dir, hab ich eine Herleitung und eine Zusammenfassung zum EEA geschrieben. Kann ich sie dir mal schicken? |
||
|
|
