Erweiterter euklidischer Algorithmus

Aufrufe: 225     Aktiv: 25.03.2023 um 11:13

0

Erläutern Sie wie man mit Hilfe des Erweiterten Euklidischen Algorithmus das

multiplikativ inverse Element mod n finden kann. Zeigen Sie dazu insbesondere

den mathematischen Zusammenhang, der dies erlaubt? 

Diese Frage melden
gefragt

Student, Punkte: -25

 
Kommentar schreiben
1 Antwort
0
Moin,
die Idee sollte klar sein; man nimmt sich $x\in \mathbb{Z}$ her und sucht $y\in \mathbb{Z}$, s.d. $x*y\equiv 1 \text{ (mod n) }$. Das ist nun äquivalent dazu, dass $x*y=1+n*z$ für $z\in\mathbb{Z}$. Das kann man umformen zu $$x*y+z*n=1$$und optimaler Weise ist einem nun das Lemma von Euklid ein Begriff. Von hier aus schaffst du es sicher alleine, wenn nicht, melde dich wieder.
LG
Diese Antwort melden
geantwortet

Student, Punkte: 3.82K

 

Kommentar schreiben