Diskrete Exponentialfunktion

Die diskrete Exponentialfunktion $b^{x}\ mod\ m$ liefert den Rest bei Divison von $b^{x}$ durch m. Synonyme Bezeichnungen sind modulare Exponentiation oder modulares Potenzieren. Die Umkehrung der diskreten Exponentialfunktion heißt diskreter Logarithmus.

Die diskrete Exponentialfunktion ist auch für große Exponenten effizient berechenbar. Für die Umkehrung, also die Berechnung des Exponenten x, bei gegebener Basis b, Modul m und gewünschtem Ergebnis, ist allerdings bis heute kein schneller Algorithmus bekannt. Die diskrete Exponentialfunktion wird daher als Einwegfunktion in Asymmetrischen Kryptosystemen verwendet.

Zur Berechnung der diskreten Exponentialfunktion kann man folgenden Algorithmus verwenden:

function expmod(x,e,m : integer) : integer;
   /* 
    Berechnet die diskrete Exponentialfunktion zur Basis e modulo m
    unter ausschließlicher Verwendung der Operationen Quadrieren
    und Multiplizieren. Der Rest wird nach jeder Operation bestimmt, 
    um große Zwischenergebnisse zu vermeiden 
   */
   var y : integer;
   begin
   if e = 0 then 
      return 1
   else 
      if e = 1 then 
         return (x mod m)
      else 
         y := expmod(x, e div 2, m);
         y := (y*y) mod m;
         if e mod 2 = 1 then
            y := (y*x) mod m;
         fi;
         return y;
      fi;
    fi;
end;

Das Verfahren benötigt höchsten 2 * log₂(e) Multiplikationen modulo n