Schnelles Potenzieren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

Inhaltsverzeichnis

1 Square & Multiply

[Bearbeiten] Square & Multiply

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

[Bearbeiten] Einsatzgebiete

Das Verfahren ist für folgende zwei 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.

[Bearbeiten] 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$

[Bearbeiten] 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; (b hat n+1 Ziffern)
m ... Modulus

Gesucht:

$res=a^c\;\bmod{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.

[Bearbeiten] Beispiel

Gegeben:

a = 2
c = 11
b = 1011

res = 1

Schleifendurchlauf 1: $b 0 = 1$

r e s = r e s 2 = 1

r e s = r e s * a = 2

Schleifendurchlauf 2: $b 1 = 0$

r e s = r e s 2 = 4

Schleifendurchlauf 3: $b 2 = 1$

r e s = r e s 2 = 16

r e s = r e s * a = 32

Schleifendurchlauf 4: $b 3 = 1$

r e s = r e s 2 = 1024

r e s = r e s * a = 2048

[Bearbeiten] Laufzeitanalyse

Bei der einfachen und langsamen Potenzierung von $a c$ multipliziert man $a$ $(c - 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 (c))$ Operationen, wogegen man $O (c)$ Operationen bei der einfachen Potenzierung benötigt. $O$ bezeichnet eine asymptotische 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.