Die modulare Exponentiation spielt in der Kryptographie sowie zum ver- als auch zum entschlüsseln von Nachrichten eine wichtige Rolle. Beim RSA-Verfahren z.B. besteht die Chiffrierung in der Berechnung von .

Verschiedene Möglichkeiten eine Potenzierung duchzuführen:

• Eine naive Methode wäre es durch eine Reihe von Multiplikationen 
  zu berechnen. Demnach wären Multiplikation notwendig.
• Eine weitere Methode wäre das Wiederholte Quadrieren:
  
• Ein effizienteres Potenzieren kann auch wie folgt durchgeführt werden:
  
• Ein gutes Rezept für ein schnelles Potenzieren ist für ein allgemeines b ins Binärsystem zu überführen:
  
  anschließend berechnet man wiederholt Quadrate von , dies erzeugt nacheinander:und multipliziert ein zum Endergebnis wenn . Daraus ergibt sich eine höchste Anzahl an Multiplikationen von .
  
  

Programmbeispiel der modularen Exponentiation

Es gilt z.Bsp.:

daraus folgt für :

Rekursiv kann die modularen Exponentiation wie folgt für mit beschrieben werden:

Eine rekursive Implementierung der obigen Rekursionsformeln mit in Python mit dem Rückgabewert als Ergebnis 1:

def modexp(m, b, n):
    if b == 0:
        return 1
    if b % 2==1:
        return modexp(m, b-1, n)*m % n
    else:
        return modexp(m, b//2, n)**2 % n
    
if __name__ == '__main__':
    print(modexp(2,4,5))

Eine iterative Implementierung von in Python nach der „naiven Methode“ sieht wie folgt aus:

def modexpIt(m, b, n):
    bs=1
    while(b > 0):
        bs *= m
        b -= 1
    erg = bs % n
    return erg
    
if __name__ == '__main__':
    print(modexpIt(2,4,5))

Das obige Beispiel verdeutlicht nocheinmal, dass für die Berechnung von   b-1 Multiplikation bzw. b-1 Schleifendurchläufe notwendig sind.
Bezugnehmend auf das Laufzeitverhalten der Iterativen Implementierung zur Berechnung von   kann man somit sagen, dass diese (für ) beträgt lineares Laufzeitverhalten.

Binäres Potenzieren

Das binäre Potenzieren ist eine effizientere Methode für die Exponentation, als die zuvor beschriebenen Verfahren. Sie funktioniert wie folgt:

Für wobei wird binär dargestellt. Für jede 1 wird nun die Operation quadrieren und multiplizieren (QM) und für jede 0 die Operation quadrieren (Q) durchgeführt. Wobei die führende 1 gestrichen werden kann, da die Binärdarstellung für immer mit einer 1 beginnt und damit auch die erste Anweisung mit QM, ergibt sich hierfür .

Beispiel:

für und .

die führende 1 wird nun gestrichen 101. Nun werden für folgende Operationen durchgeführt:

QM Q QM

Für ergibt sich nun:

• QM
• Q
• QM

Kongret für erhält man:

In der Programmiersprache Python lässt sich das Ganze wie folgt beschreiben:

'''Umwandlung in binaer und Ergebnis als Liste zurueckliefern'''
def sammleBin(exponent):
    binListe = []
    tmpgerade = 0
    if exponent % 2 == 0:
        tmpgerade = exponent
        exponent = exponent + 1
    while exponent != 0:
        binListe.insert(0,exponent % 2)
        exponent = exponent // 2
    if tmpgerade != 0:
        binListe[len(binListe)-1] = 0
    '''erstes Element aus Liste entfernen'''
    del binListe[0]
    return binListe

'''Entsprechende Operationen durchfuehren (QM oder Q)'''
def binPotenz(basis, expo):
    binListe = sammleBin(expo).copy()
    wert = basis
    for i in range(0, len(binListe)):
        if(binListe[i] == 1):
            wert = basis * (wert**2)
        else:
            wert = wert**2
    return wert

if __name__ == '__main__':
    print("",binPotenz(5, 13))

Nähere Informationen über die Binäre Exponentiation findet man bei Wikipedia.