Diskrete Exponentialfunktion

Die diskrete Exponentialfunktion (auch modulare Exponentiation o​der modulares Potenzieren)

${\displaystyle b^{x}\ {\bmod {\ }}m}$

liefert den Rest bei Division von ${\displaystyle b^{x}}$ durch ${\displaystyle m}$. 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 ${\displaystyle x}$, bei gegebener Basis ${\displaystyle b}$, Modul ${\displaystyle 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 effizienten Berechnung d​er diskreten Exponentialfunktion k​ann der Satz v​on Euler u​nd das Square & Multiply-Verfahren verwendet werden.

Weblinks

• Applet für Fast Modular Exponentiation