euklidischen Algorithmus?
Hallo Leute,
Kann mir jemand bitte hier helfen
Ich muss der Inversen zu e modulo berechnen. Ich muss die Ergebnisse von d und k wie auf dem gemalt ist aufschreiben. Aber ich weiß gar nicht wie das geht
1 Antwort
Du nutzt dafür den erweiterten Euklidischen Algorithmus - die Seite von Wikipedia gibt da auch ein Beispiel und du wirst Informationen dazu bestimmt auch in deinem Skript finden
Kurz: Du führst zuerst den normalen euklidischen Algorithmus mit e und phi(n) durch.
Deine Berechnungen stellst du dann jeweils auf den Rest um und setzt die Zeilen - von Rest 1 an gesehen - ineinander ein, behältst aber die Multiplikationen bei
Schau dir einfach das Beispiel hinter dem Wikipedia-Link an - direkt unter "Funktionsweise am Beispiel"
Ich kanns aber gerne nochmal auflisten, aber mit einem kleineren Beispiel, weil es jetzt fast 3 Uhr morgens ist.
Nehmen wir einfach mal den ggT von 3 und 14
14 = 4 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0
Die letzte Zeile ist für die weiteren Berechnungen irrelevant, kann also ignoriert werden. Die anderen Zeilen stellen wir jetzt einfach um, sodass der Rest alleine stehet
2 = 14 - 4 * 3
1 = 3 - 1 * 2
Dann fangen wir beim Rest "1" an und schauen, welchen Rest wir einsetzen können - bei dem Beispiel bleibt eben nur die 2 und da 2 = 14-4*3, ersetzen wir die zwei eben mit der anderen Seite
1 = 3 - 1 * 2 = 3 - 1 * (14 - 4 * 3) = 3 - 1 * 14 + 4 * 3
Das ganze fassen wir jetzt noch zusammen:
1 = 3 - 1 * 14 + 4 * 3 = -1 * 14 + 5 * 3
Wenn man das jetzt ausrechnet, ergibt sich 1 = -14 + 15; die Berechnung ist also korrekt, da auch tatsächlich 1 rauskommt
Ich hatte diese Thema noch nie gehabt. Ich muss das jetzt nur kurz machen, wegen meine Facharbeit, zur Verschlüsselungsverfahren. Ich weiß gar nicht wie ich die Zahlen schreibe damit ich die berechne. Also welcher Zahl kommt wohin? Ich habe Youtube videos angeschaut, aber trotzdem nicht so verstanden.