18^23 mod 77 [RSA-Verschlüsselung]

Question

ich wüsste gerne wie ich 18²³ mod 77 per Hand ausrechnen kann.

Ich weiss, dass 2 mod 77 herauskommt, aber wie komme ich darauf?

Vielen Dank!

Answer 1

Es gibt einen Pow-Mod-Algorithmus zum Abkürzen: der Iterationsrechner Beispiel 122

http://www.gerdlamprecht.de/Roemisch_JAVA.htm#ZZZZZ0122  

zeigt dies: einfach Variable a nach 18 und b nach 23 ändern:

solange b ungerade, aC[d+1]=(aC[d]*aB[i]) Mod c

b wird bei jeder Iteration halbiert, bis b kleiner 1

Das Ergebnis steht im letzten aC und auch durch die Abschlußberechnung in b.

5 Schritte reichen -> und das kann man auch mit noch größeren Zahlen "per Hand".