Zahlentheoretische Algorithmen der Kryptografie

Modulare Exponentiation iterativ

 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 links nach rechts aus.

Idee

Die Berechnung folgt der Auswertung einer Binärzahl nach dem Horner-Schema. So wird beispielsweise 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 m13:

m((((0) · 2 + 1) · 2 + 1) · 2 + 0) · 2 + 1   =   m13

Unter Anwendung der Regeln für die Potenzrechnung ergibt sich somit

((((m0)2 · m1)2 · m1)2 · m0)2 · m1   =   m13

 

Zur Auswertung einer k-Bit-Binärzahl sind k Multiplikationen 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 Multiplikationen erforderlich (bzw. sogar weniger Multiplikationen, wenn die Multiplikation mit m0 = 1 weggelassen wird).

Programm

Das entsprechende Programm in der Programmiersprache Python ist im Folgenden angegeben. Nach jeder Multiplikation wird das Zwischenergebnis modulo n reduziert. Mit binary(e) wird die Binärdarstellung 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:me 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ärdarstellung einer Zahl e als String lässt sich mit folgender Funktion unter Benutzung der Python-Funktion bin erzeugen:

def binary(e):
    return bin(e)[2:]

Zusammenfassung

Aus der Auswertung einer Binärzahl nach dem Horner-Schema lässt sich ein Verfahren zur schnellen Exponentation ableiten. Hierzu wird die Binärdarstellung des Exponenten herangezogen. Bei einem k-Bit-Exponenten sind für die Exponentation höchstens 2k Multiplikationen 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ärdarstellung 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 Quadratzahlen modulo n (sogenannte quadratische Reste) erzeugt.

 

Weiter mit:   [Modulare Exponentiation rekursiv]   [Primzahltest]   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