Umkehrung Euklidischer Algorithmus

Neue Frage »

Jan0000 Auf diesen Beitrag antworten »
Umkehrung Euklidischer Algorithmus
Hallo, ich habe eine Frage zur RSA-Berechnung, besser gesagt zum Algoritmus von Euklid.
Ich habe eine Beispielrechnung gefunden:



Den ersten Teil kann ich nachvollziehen, den zweiten auch, bis auf die letzte Zeile.
Wie komme ich von der vorletzten Zeile auf die letzte, bzw. wo kommen die 29 und 36 her?

Vielen Dank
Jan
dudidude Auf diesen Beitrag antworten »

machs dir einfacher



fasse mehr zusammen ist übersichtlicher
jan0000 Auf diesen Beitrag antworten »

Ok, danke, aber ich verstehe nicht wieso die 4*15 in der zweiten Zeile weggelassen und stattdessen die 29 eingefügt werden kann?
Der Schritt von deiner 3 zur 4 Zeile ist klar, da wird für die 15 dann 77-62 eingesetzt, aber wo kommt die 36 in der letzten Zeile her?

Danke
RavenOnJ Auf diesen Beitrag antworten »

29 + 7 = 36
jan0000 Auf diesen Beitrag antworten »

Dankeschön. Aber warum kann ich 29 und 7 einfach addieren? Ich verstehe immer noch nicht was mit den 4 *15 gemacht wurde, das ist doch 60, wo ist die?
Sorry, ich glaube ich stehe grade auf dem Schlauch.
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von jan0000
Dankeschön. Aber warum kann ich 29 und 7 einfach addieren? Ich verstehe immer noch nicht was mit den 4 *15 gemacht wurde, das ist doch 60, wo ist die?
Sorry, ich glaube ich stehe grade auf dem Schlauch.


Bist du gerade etwas blind?? Die Gleichung heißt:


Ich hab mal alles relevante rot gemacht.
 
 
jan0000 Auf diesen Beitrag antworten »

Ne, dann liegt es wohl an meiner mangelnden Mathekenntnis
Ich verstehe es ehrlich gesagt immer noch nicht verwirrt
jan0000 Auf diesen Beitrag antworten »

Ah, ok, wie man auf die 36 kommt kann ich, glaube ich, jetzt nachvolziehen:
(29*77-1) / 62 = 36

Aber das mit der 29 verstehe ich nicht
jan0000 Auf diesen Beitrag antworten »

Achhhhsoo, entschuldigung wegen den Doppelposts, jetzt habe ich es verstanden!
1-4*(-7)= 29 und -7-29= 36
Was ich nicht wusste ist, dass sich z.b x= 29 aus dem alten y wert minus dem
aktuellen Multiplikator mal dem alten x Wert berechnet, da ich den Algorithmus von
Euklid nicht kannte und dachte ich muss die Klammern ausmultiplizieren.

Dankeschön
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »