Was ist mit Schneller Exponentiation gemeint?

Question

Hallo Community, 

in der Vorlesung hatten wir letztens den Begriff "Schnelle Exponentiation" im Zusammenhang mit Modulo-Rechnung. Ich habe aber die rechnung des Profs nicht verstanden beziehungsweise weiß nicht, wie man das auf andere Fälle anwendet.

Könnte mir einer vielleicht anhand eines Beispiels das erklären? Es sollen damit Sachen wie a^b mit großen b vereinfacht werden können.

Answer 1

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

Answer 2

Leider muss ich zugeben, auch nicht ganz sicher zu sein. Aber da es um einen Zusammenhang mit Modulo-Rechnung geht, vermute ich eine Fragestellung, wie die folgende: Bestimme "17¹⁰²⁴ mod 13" mit möglichst wenig Rechenaufwand. Wenn das die Frage ist, würde ich so vorgehen 17⁶≡1 mod 13. Dann 17¹⁰²⁰≡1 mod 13. Außerdem 17⁴≡9 mod 13 und daher 17¹⁰²⁴ ≡9 mod 13

Comments

Roland, 

ich denke, dass Deine Erklärung in die richtige Richtung geht und Rechenaufwand gespart werden soll. Ich kenne "schnelle Exponentiation" tatsächlich im Zusammenhang mit großen Exponenten, die bezüglich eines Moduls berechnet werden sollen, z.B. $$31^{99}\mod 101$$ Mit diesem Verfahren kann man gute Aufgaben auf Übungsblättern und in Prüfungen stellen, wie etwa das Berechnen von multiplikativen Inversen durch schnelle Exponentiation in Kombination mit dem "kleinen Fermat".

Ein schönes Wochenende!

André, savest8