Modulare Exponentiation (Variante 2)

Algorithmen zur schnellen Exponentiation basieren auf der Auswertung der Binärdarstellung des Exponenten. Die Auswertung kann dabei entweder von links nach rechts oder von rechts nach links erfolgen. Das folgende Verfahren wertet die Binärdarstellung von rechts nach links aus. Der Vorteil besteht darin, dass die Binärdarstellung nicht explizit vorliegen muss, sondern sie wird während der Berechnung implizit erzeugt.

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 Potenzrechnung ergibt sich

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

Wenn die Binärdarstellung 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 vorhergehende Potenz quadriert wird.

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

Die folgende Gegenüberstellung zeigt das Programm zur Auswertung einer binär dargestellten Zahl e der Länge k von rechts nach links sowie das entsprechende 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 Multiplikation 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 Schleifendurchlauf rechtsgeschoben 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 Multiplikation wird das Zwischenergebnis modulo n reduziert.

Funktion modexp

Eingabe:

Zahl m, Exponent e, Modul n

Ausgabe:

m^e mod n

Methode:

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 Schleifendurchlauf ganzzahlig durch 2 geteilt wird.

def modexp(m, e, n):
    s=1
    while e>0:
        if e%2==1:
            s=s*m%n
        m=m*m%n
        e=e//2
    return s

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

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

Weiter mit: [Standardverfahren der modularen Exponentiation] oder

Modulare Exponentiation (Variante 2)

Idee

Programm

Zusammenfassung