18^23 mod 77 [RSA] - Rechenweg gesucht

Question

Ich wüsste gerne wie ich 18^23 mod 77 per Hand ausrechnen kann.

Ich weiß, dass 2 mod 77 herauskommt, aber wie komme ich darauf? Die Antwort des Feeds aus dem Jahr 2015 hat mir leider nicht weitergeholfen.

Vielen Dank!

Answer 1

Es gilt:
x^(a+b) mod c = (x^a mod c * x^b mod)mod c

Damit kannst du dein Ergebnis Stück für Stück vereinfachen.

Hier ist das noch einmal mit Beispielen erklärt:
https://medienwissenschaft.uni-bayreuth.de/inik/material/email_nur_fuer_dich/3_verschluesseln/3.3_asymmetrisch_verschluesseln/Modulares%20Potenzieren%20-%20AB.pdf

Kleiner Hinweis noch:
Wenn du 18 = 2*9 schreibst, erhältst du:
(2*9)^23 = 2^23 * 9^23

Da kannst du dann das hier drauf anwenden:
a*b mod c = (a mod c * b mod)mod c