Power

In dieser Aufgabe sollen schnelle Methoden des Potenzierens untersucht werden.

Implementieren Sie dazu zunächst eine langsame Variante. Ihre Lösung muss rekursiv sein und darf keine Schleifen enthalten. Verwenden Sie dazu die Tatsache, dass man die Power-Funktion auch induktiv definieren kann:

• a⁰ mod n = 1 (Induktionsanfang)
• a^e mod n = a * (a^e-1mod n) (Induktionsschritt)

Zählen Sie die notwendigen rekursiven Aufrufe der Methode powerMod.

 

Implementieren Sie nun eine schnelle rekursive Variante. Nutzen Sie dazu die Beobachtung, dass man den Induktionsschritt auch ausdrücken kann als:

• (a^e/2 mod n)², wenn e gerade ist
• a * (a^(e-1)/2 mod n)², sonst
  

Hinweis: Berechnen Sie den Wert a^e/2 nicht zweimal!