Übung 2

3. November 2003 (Abgabe 12. November 2003)

Aufgabe 1 (2 Punkte)

Definieren Sie eine Funktion, die die multiplikative Inverse (Modulo p) von einer Zahl x durch einen sequentiellen Test der Zahlen 1 bis p-1 findet. Dabei soll p eine Primzahl sein.

Aufgabe 2 (6 Punkte)

Implementieren Sie den RSA-Algorithmus für die Zahlen p=17 und q=23. Testen Sie die rsa_encode- und rsa_decode-Funktionen! Verwenden Sie eine schnelle Methode zur Berechnung der Exponentialfunktion.

Aufgabe 3 (2 Punkte)

Definieren Sie eine Funktion, die eine positive Dezimalzahl in 8-Tupel von Bits verwandelt. Gehen Sie wie in der Vorlesung vor, indem Sie die Zahl wiederholt dividieren.

Aufgabe 4 (6 Punkte) Achtung! Änderung!

Definieren Sie die Funktionen add, sub für 5-Tupel von Bits (vom Typ Int), die Zweierkomlementzahlen darstellen.

Aufgabe 5 (8 Punkte)

Definieren Sie die Funktionen add, sub, mul und div für rationale Zahlen. Die Zahlen sollen 2-Tupel von Ganzen Zahlen sein, wie sie in der Vorlesung eingeführt wurden (2-Tupel von Int). Die Zähler und Nenner sollen nach der Operation teilerfremd sein. Um dies zu erreichen, können die die Haskell-Funktion gcd verwenden.