Square-And-Multiply-Methode zum Potenzieren

Eine Methode um schnell $a^d\mathrm{mod}n$ zu berechnen.

Diese Methode lässt sich rekursiv definieren als:

$c_0=a\mathrm{mod}n$ $c_{i+1}=c_i^2\mathrm{mod}n$ $d_0=d$ $d_{i+1}=\lfloor \frac{d_i}{2}\rfloor$ ${\delta }_i=d_i\mathrm{mod}2$ $b_0=a^{{\delta }_0}\mathrm{mod}n$ $b_{i+1}=b_i{c}_{i+1}^{{\delta }_{i+1}}\mathrm{mod}n$ Ist $d_i\le 1$, so ist $b_i=a^d\mathrm{mod}n.$

Laufzeit

Die Laufzeit ist durch die Größe von $d$ beschränkt. In jeder Iteration wird $d_i$ halbiert. Wir berechnen also schnell, dass wir nur $l=\lfloor {\log }_{2}d\rfloor <3.33{\log }_{10}d$ Schleifenwiederholungen brauchen. Wir müssen also $l$ mal ein Quadrat bilden und höchstens $l$ Multiplikationen durchführen.

Die Laufzeit lässt sich also mit $O((\log n{)}^3)$ abschätzen.

Variante 2

In der zweiten Variante versuchen wir den Exponenten stückweise kleiner zu machen. Dabei müssen wir dann immer nur kleine Potenzen berechnen, da die Modulo Operation die Zahlen immer kleiner gleich $n$ hält.

Wir verwenden also einmal für gerades $d$ $b\cdot c^d\equiv b\cdot {\left(c^2\mathrm{mod}n\right)}^{\frac{d}{2}}\mathrm{mod}n$ und für ungeraded $d$ $b\cdot c^d\equiv (bc\mathrm{mod}n)\cdot c^{d-1}\mathrm{mod}n.$ Algorithmisch lässt sich auch dieses Verfahren rekursiv definieren, mit:

$b_0=1,c_0=a\mathrm{mod}n,d_o=d.$ Wenn $d_i=0$, dan ist $b_i=a^d\mathrm{mod}n$.

Für $d_i>0$ und $d_i$ gerade: $b_{i+1}=b_i,c_{i+1}=c_i^2\mathrm{mod}n,d_{i+1}=\frac{d_i}{2}.$ Für $d_i>0$ und $d_i$ ungerade: $b_{i+1}=b_i{c}_i\mathrm{mod}n,c_{i+1}=c_i,d_{i+1}=d_i-1.$

code paste here

Variante 3

code paste here