Schnelles Potenzieren

Unter dem Schnellen Potenzieren versteht man ein mathematisch optimiertes Verfahren, dessen bekanntester Vertreter das Square & Multiply ist. Es stellt eine Möglichkeit dar, um die Berechnung von natürlichen Zahlen mit großen Exponenten zu beschleunigen, in dem es versucht, Rechenoperationen zu ersparen.

Square & Multiply

Das Square & Multiply Verfahren beschreibt eine Methode, um schnell Potenzen zu berechnen.

Einsatzgebiete

Das Verfahren ist für folgende 2 Fragestellungen geeignet:

• $a^{c}$
• $a^{c}\,\mathrm {mod} \,n$

Das Verfahren ist nicht nur auf die Multiplikation beschränkt, sondern kann für verschiedenste Operationen (z.B. Elliptische Kurven-Addition) adaptiert werden.

Verfahren

Square & Multiply nutzt die Tatsache, dass $a^{c}$ eindeutig als $a^{c}=a^{1\cdot b_{0}}\cdot a^{2\cdot b_{1}}\cdot a^{4\cdot b_{2}}\cdot \dots \cdot a^{2^{n}\cdot b_{n}}$ geschrieben werden kann, wobei $b_{i}\in \{0,1\}$ und $\sum _{i=0}^{n}b_{i}\cdot 2^{i}=c$.

Dies kann man wiederum umformen und erhält folgende Form $a^{c}=a^{b_{0}}(a^{b_{1}}(\dots (a^{b_{n-1}}(a^{b_{n}})^{2})^{2}\dots )^{2})^{2}$

Algorithmus

Gegeben:

• a ... Zahl die Potenziert werden soll
• c ... Potenz
• b ... Binärdarstellung von c, wobei das höchstwertigste Bit an der Stelle 0 steht und das niederwertigste Bit an der Stelle n
• m ... Modulus

Gesucht:

• $res=a^{c}\mod {m}$

Ablauf:

Square & Multiply
res=1 for i=0..n res = res^2 mod m if b_i = 1 res = res * a mod m end-if end-for

Wenn keine modulare Reduzierung von Nöten ist, wird diese einfach weggelassen.

Möchte man die Punktmultiplikation für elliptische Kurven implementieren, muss man die Quadrierung und die Multiplikation durch das jeweilige Äquivalent ersetzen. Der adaptierte Algorithmus hätte folgende Form.

Gegeben:

• P ... Punkt, der multipliziert werden soll (Punktmultiplikation)
• c ... Multiplikator
• b ... Binärdarstellung von c, wobei das höchstwertigste Bit an der Stelle 0 steht und das niederwertigste Bit an der Stelle n
• INF ... Unendlichkeits- oder Nullpunkt (neutrales Element)

Gesucht:

• $Q=c\cdot P$

Square & Multiply für elliptische Kurven
Q=INF for i=0..n Q = 2*Q if b_i = 1 Q = Q + P end-if end-for

Square & Multiply ist streng genommen der falsche Begriff. Es müsste eigentlich Double & Add heißen.

Beispiel

Gegeben:

• a = 2
• c = 11
• b = 1011

res = 1

• Schleifendurchlauf 1: $b_{0}=1$

res = res^2 = 1

res = res * a = 2

• Schleifendurchlauf 2: $b_{1}=0$

res = res^2 = 4

• Schleifendurchlauf 3: $b_{2}=1$

res = res^2 = 16

res = res * a = 32

• Schleifendurchlauf 4: $b_{3}=1$

res = res^2 = 1024

res = res * a = 2048

Laufzeitanalyse

Bei der einfachen und langsamen Potenzierung von $a^{c}$ multipliziert man $a$ $(p-1)$-mal mit sich selbst. Beim Square & Multiply werden lediglich $\log _{2}(c)$ Schleifendurchläufe benötigt. In jedem Schleifendurchlauf kommt es zu einer Quadrierung (wobei die erste Quadrierung vernachlässigt werden kann) und eventuell einer Multiplikation. Asymptotisch kommt man auf $O(\log _{2}(p))$ Operationen, wogegen man $O(p)$ Operationen bei der einfachen Potenzierung benötigt. $O$ bezeichnet eine asymptische obere Schranke für das Laufzeitverhalten des Algorithmus. Wie man leicht einsieht, ist das Square & Multiply Verfahren sehr viel effizienter als das einfache Verfahren. Dieser verringerte Anspruch an die Rechenleistung ist bei großen Basen und Exponenten enorm.