Warum kann 47 * d = 1 mod 60 mit dem erweiterten euklidischen Algorithmus gelöst werden?

Aufrufe: 611     Aktiv: 29.12.2020 um 21:18
0

(Bezug auf das Video: RSA-Verschlüsselung Beispiel)

Um die Gleichung 47 * d = 1 mod 60 zu lösen wird 47x + 60y = 1 gelöst und das daraus resultierende x für d eingesetzt.

Ich komme gerade einfach nicht darauf warum das so funktioniert? Kann es mir vielleicht jemand erklären?

Diese Frage melden
gefragt

Student, Punkte: 217

 
Kommentar schreiben
1 Antwort
1

Ist dir klar, warum man mit dem erweiterten euklidischen Algorithmus \(x\) und \(y\) finden kann, so dass \(47x+60y=1\) gilt? Wenn wir \(\mod 60\) rechnen, steht da aber \(47x+0=1\), da \(60y = 0 \mod 60\) gilt. Und dann ist \(x\) folglich unser \(d\), so dass \(47d=1 \mod 60\) gilt.

Diese Antwort melden
geantwortet

Selbstständig, Punkte: 30.55K

 
Dankesehr, ja klar, 60y ist ja 0, warum bin ich da nicht gleich drauf gekommen ^^? - Vielen Dank! :)   ─   mrswindy 29.12.2020 um 21:16

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Cauchy wurde bereits informiert.