MathFox,
schnelle Exponentiation wird üblicherweise verwendet, um "große" Exponenten modulo n "schnell" berechnen zu können. Ich möchte Dir das Ganze anhand einer kleinen Beispielaufgabe erläutern. Nehmen wir an, Du willst das multiplikative Inverse von 31 in $$\mathbb{Z}/101\mathbb{Z}$$ nicht mit dem (erweiterten) euklidischen Algorithmus, sondern mit kleinen Satz von Fermat bestimmen. 101 ist eine Primzahl, d.h. $$\varphi(101)=101-1=100\wedge 31^{100}\equiv 1\mod 101$$Es ist aber auch $$31^{100}=31^{99}\cdot 31\equiv 1\mod 101$$ Nun kannst Du das Ergebnis so stehen lassen, doch wir wollen den Wert von $$3^{99}$$ explizit ausrechnen. In Prüfungen zugelassene Taschenrechner würden vermutlich versagen, wenn Du mit ihnen $$31^{99} \mod 101$$ zu berechnen versuchst und genau hier setzen wir mit schneller Exponentiation an. Üblicherweise wandelt man den Exponenten zunächst in eine Binärzahl der Form $$x_0x_1x_2...x_n\text{ mit }x_i\in\{0,1\}\wedge0\leq i\leq n$$ um (ohne führende Null). Danach betrachten wir die Länge unserer Binärzahl, d.h. wie viele Stellen (aus Nullen und Einsen) sie besitzt. Für unseren Fall gilt: $$99_{(10)}=1100011_{(2)}$$ und damit hat die Binärzahl die Länge 7. Wir führen also insgesamt "nur" 7 Zwischenrechnungen aus, um die Aufgabe zu lösen, nämlich folgende:
$$31^{2^0} = 31$$
$$31^{2^1} = 31^2 = 961\equiv 52\mod 101$$
$$31^{2^2} = 31^4=52^2=2704\equiv 78\mod 101$$
$$31^{2^3} = 31^8=78^2= 6084\equiv 24\mod 101$$
$$31^{2^4} =31^{16}=24^2=576\equiv 71\mod 101$$
$$31^{2^5} = 31^{32}=71^2=5041\equiv 92\mod 101$$
$$31^{2^6} = 31^{64}=92^2= 8464\equiv 81 \mod 101$$
Es werden alle Ergebnisse, die bei der Exponentiation entstanden sind und bei denen keine 0 an der entsprechenden Stelle der Binärzahl steht, miteinander multipliziert. Im Prinzip hättest Du Dir die Berechnung für $$31^{2^2}\wedge 31^{2^3}\wedge31^{2^4}$$ sparen können, da an den entsprechenden Stellen in der Binärzahl eine 0 steht, doch für das Berechnen der Folgeergebnisse durch einfaches Quadrieren bestimmt man diese Ergebnisse einfach mit. Schlussendlich erhältst Du für unser Beispiel
$$31\cdot 52\cdot 92\cdot 81 = 12012624 \equiv 88 \mod 101$$ Mit der folgenden Rechnung kannst Du das Ergebnis verifizieren:
$$31 \cdot 88\equiv 1\mod 101$$
Ich hoffe, dass ich Dir damit weiterhelfen konnte!
André, savest8