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 rechts nach links aus. Der Vorteil besteht darin, dass die Binär­darstellung nicht explizit vorliegen muss, sondern sie wird während der Berechnung implizit erzeugt.

Idee

Eine binär dargestellte Zahl lässt sich in folgender Weise auswerten, hier dargestellt am Beispiel von 13 = 1101:

13   =   8·1  +  4·1  +  2·0  +  1·1

Hieraus lässt sich ein Verfahren zur schnellen Exponentiation ableiten:

m¹³   =   m^{8·1  +  4·1  +  2·0  +  1·1}

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

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

Wenn die Binär­darstellung des Exponenten von rechts nach links abgearbeitet wird, lassen sich die Potenzen von m nebenbei erzeugen, indem mit m begonnen wird und danach jeweils die vorher­gehende Potenz quadriert wird.

Auf diese Weise genügen höchstens 2 log(e) Multi­plikationen zur Berechnung von m^e nach diesem Verfahren.

Programm

Die folgende Gegenüber­stellung zeigt das Programm zur Auswertung einer binär dar­gestellten Zahl e der Länge k von rechts nach links sowie das ent­sprechende Programm zur Exponentiation einer Zahl m mit dem Exponenten e.

int s=0, p=1;
for (int i=0; i<k; i++)
{
    if (e[i]==1)
        s=s+p;
    p=p+p;
}

int s=1, p=m;
for (int i=0; i<k; i++)
{
    if (e[i]==1)
        s=s*p;
    p=p*p;
}

Aus dem zweiten dieser Programme ist das folgende Programm zur modularen Multi­plikation beliebig großer Zahlen (Java-Typ java.math.BigInteger) abgeleitet. Die Folge der Bits des Exponenten e wird erzeugt, indem immer das letzte Bit von e betrachtet wird und e nach jedem Schleifen­durchlauf rechts­geschoben wird. Die Schleife endet, wenn alle Bits von e verarbeitet sind, wenn also e den Wert 0 erreicht hat. Die Variable p wird direkt durch m ersetzt. Nach jeder Multi­plikation wird das Zwischen­ergebnis modulo n reduziert.

Funktion modexp

Eingabe:

Zahl m, Exponent e, Modul n

Ausgabe:

m^e mod n

Methode:

1. BigInteger modexp(BigInteger m, BigInteger e, BigInteger n)
   {
       BigInteger s=BigInteger.ONE;
       while (!e.equals(BigInteger.ZERO))
       {
           if (e.testBit(0))
               s=s.multiply(m).mod(n);
           m=m.multiply(m).mod(n);
           e=e.shiftRight(1);
       }
       return s;
   }
   

In Python ergibt sich das folgende Programm. Die Folge der Bits des Exponenten ergibt sich, indem immer das letzte Bit von e als Rest bei Division durch 2 erzeugt wird und e nach jedem Schleifen­durchlauf ganzzahlig durch 2 geteilt wird.

Zusammenfassung

Das hier dargestellte Verfahren zur schnellen modularen Exponentiation m^e mod n erfordert O(log e) Multi­plikationen und Reduktionen modulo n, d.h. die Zeit­komplexität verhält sich höchstens linear zur Länge des Exponenten in Bit.

Im Gegensatz zum Standard­verfahren zur modularen Exponentiation ist es nicht erforderlich, dass die Binär­darstellung des Exponenten explizit vorliegt, sondern sie wird während der Berechnung implizit erzeugt.

Für die modulare Exponentiation im Zusammenhang mit dem Miller-Rabin-Primzahltest ist das hier angegebene Verfahren jedoch nicht geeignet