Berechnungsverfahren

Algorithmen zur schnellen Exponentiation basieren auf der Auswertung der Binär­darstellung des Exponenten. Die Auswertung kann dabei entweder von links nach rechts oder von rechts nach links erfolgen. Das folgende Verfahren wertet die Binär­darstellung von links nach rechts aus.

Idee

Die Berechnung folgt der Auswertung einer Binärzahl nach dem Horner-Schema. So wird beispiels­weise die Binärzahl 1101 nach dem Horner-Schema wie folgt ausgewertet:

((((0) · 2 + 1) · 2 + 1) · 2 + 0) · 2 + 1   =   13

Daraus ergibt sich unmittelbar das Verfahren zur Exponentiation, hier also zur Berechnung von m¹³:

m^{((((0) · 2 + 1) · 2 + 1) · 2 + 0) · 2 + 1}   =   m¹³

Unter Anwendung der Regeln für die Potenz­rechnung ergibt sich somit

((((m⁰)² · m¹)² · m¹)² · m⁰)² · m¹   =   m¹³

Zur Auswertung einer k-Bit-Binärzahl sind k Multi­plikationen mit 2 und k Additionen erforderlich (bzw. sogar weniger Additionen, wenn die Addition von 0 weggelassen wird). Entsprechend sind für die Exponentiation nach diesem Verfahren bei einem k-Bit-Exponenten k Quadrate und k Multi­plikationen erforderlich (bzw. sogar weniger Multi­plikationen, wenn die Multi­plikation mit m⁰ = 1 weggelassen wird).

Programm

Das entsprechende Programm in der Programmier­sprache Python ist im Folgenden angegeben. Nach jeder Multi­plikation wird das Zwischen­ergebnis modulo n reduziert. Mit binary(e) wird die Binär­darstellung des Exponenten e in Form eines Strings erzeugt, die Implementation dieser Funktion ist weiter unten angegeben.

Funktion modexp

Eingabe:

Zahl m, Exponent e, Modul n

Ausgabe:

m^e mod n

Methode:

1. def modexp(m, e, n):
       s=1
       for b in binary(e):
           s=s*s % n
           if b=="1":
               s=s*m % n
       return s
   

Die Binär­darstellung einer Zahl e als String lässt sich mit folgender Funktion unter Benutzung der Python-Funktion bin erzeugen:

Zusammenfassung

Aus der Auswertung einer Binärzahl nach dem Horner-Schema lässt sich ein Verfahren zur schnellen Exponentation ableiten. Hierzu wird die Binär­darstellung des Exponenten herangezogen. Bei einem k-Bit-Exponenten sind für die Exponentation höchstens 2k Multi­plikationen erforderlich.

Die schnelle modulare Exponentiation lässt sich auch in einfacher Weise als rekursive Implementierung realisieren.

Ein alternatives iteratives Verfahren zur schnellen modularen Exponentiation arbeitet die Binär­darstellung beginnend beim letzten Bit ab.

Insbesondere für den Miller-Rabin-Primzahltest ist jedoch das hier angegebene Verfahren zu bevorzugen, da es in der Variablen s eine Folge von Quadrat­zahlen modulo n (sogenannte quadratische Reste) erzeugt.