Modulare Exponentiation iterativ (Variante 2)

 aufwärts

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.

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:

m13   =   m1  +  4·1  +  2·0  +  1·1

Unter Anwendung der Regeln für die Potenzrechnung ergibt sich

m13   =   (m8)1 · (m4)1 · (m2)0 · (m1)1

 

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 me nach diesem Verfahren.

Programm

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:me 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 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

Zusammenfassung

Das hier dargestellte Verfahren zur schnellen modularen Exponentiation me 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.

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

 

Weiter mit:   [Modulare Exponentiation iterativ (Variante 1)]   [Modulare Exponentiation rekursiv]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 12.06.2001   Updated: 08.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik