21. Potenzen und Kleiner Satz des Fermat
Nachdem wir letztes Mal Primzahlen gefunden haben und Multiplikation modulo n betrieben haben, wollen wir heute Potenzen modulo n betrachten.
1. Potenz-Tabelle Analog zur Multiplikationstabelle, wollen wir diesmal potenzieren modulo einer positiven ganzen Zahl n. Wenn wir b^e\pmod{n} ausrechnen, haben wir mathematisch 2 Möglichkeiten: Wir können entweder mit großen ganzen Zahlen rechnen und zunächst b^e ausrechnen und dann den Rest modulo n bestimmen. Oder wir multiplizieren in einem fort, d.h. fangen bei b^2\equiv b * b \pmod{n} an, bestimmen den Rest modulo n und gehen dann weiter zu b^3\equiv b^2 * b \pmod{n}.