Potenzen in Modulo: Zeigen, dass (N^e mod n)^d mod n = (N^e)^d mod n

Question

wollte fragen, nach welchem Satz und warum gilt: (Also mich würde ebenfalls der Beweis interessieren)

(N^e mod n)^d mod n = (N^e)^d mod n

Ergänzung:

Vereinfachung:

(N mod n)^d mod n = N^d mod n

Keine Ahnung warum ich es anfangs so kompliziert geschrieben habe. Allerdings komm ich nicht drauf wie ich zeigen kann, dass dies gilt.

Answer 1

Habt ihr schon gezeigt das

(a * b) mod n = ((a nod n) * (b mod n)) mod n ?

Dann wäre der Rest ja jetzt ein Klacks. Dann kannst du das mit der vollständigen Induktion beweisen.

Comments

Ich hab in nem Buch mir das RSA Verfahren angesehen aber dort ist vieles nicht bewiesen und hier konnte ich auch nichts im I-Net finden. Und nein leider habe ich dies auch noch nicht bewiesen.

(ja gut wenn ich die Aussage oben als Voraussetzung nehme ist es einfach)

---

Könntest du mir den Beweis für die Behauptung von dir geben?

---

habs jetzt

schade dass du mir die Lösung nicht schnell mal geben konntest - kann die leider nicht richtig aufschreiben da ich keine unteren Gaußklammern habe

---

Den Beweis findet man unter anderem hier

http://www.math.uni-bremen.de/didaktik/ma/ralbers/Veranstaltungen/ArithmAP0809/Material/SkriptWiSe4_KongMod.pdf