Lösung - Restklassen 05

Square and Multiply-Algorithmus

Man wandelt den Exponenten in eine Dualzahl um:

Dies kann zusammengefasst werden in einen Algorithmus:

  x = 1
  Konvertierung von n in eine Binärzahl (Dualzahl)
  n = (bkbk-1...b0)2
  Vom ersten Bit bis zum letzten Bit führe aus
     if bi = 0
       x = x2
     else
       x = a x2
     return x
  

Beispiel:
Berechne 3²⁰ mod 25

Zuerst wandeln wir 20 in eine Binärzahl (Dualzahl) - anschließend wenden wir den Algorithmus an.

Lösung = 1

[ Schliessen ]