Aufgabe 2:  (Schnelle Exponentiation)

Implementieren Sie eine rekursive Funktion

modexp(m, e, n)

zur Berechnung von

m^e mod n

 

Benutzen Sie für die Exponentiation folgende Rekursions­formel

 

Führen Sie die Berechnungen der Rekursions­formel jedoch modulo n durch. Reduzieren Sie dabei jedes Zwischen­ergebnis modulo n, damit die beteiligten Zahlen nicht zu groß werden.

Benutzen Sie das Programm, um zu berechnen, welcher Wochentag heute in 2⁹⁹⁹ Tagen ist.

Wenden Sie diese Methode an, um die Exponentiation p^k eines Punktes p einer elliptischen Kurve in der Methode __pow__ der Klasse EcPoint zu berechnen.