Aufgabe 5:  (Miller-Rabin-Test, zufällige Primzahl)

1. Implementieren Sie die Funktion

   isCompositeWitness(a, n)

   aus der Vorlesung, die true zurückgibt, wenn die Zahl a ein Zeuge dafür ist, dass die Zahl n zusammen­gesetzt ist.

    

2. Schreiben Sie eine Funktion

   isCompositeMillerRabin(n, k)

   die k zufällig gewählte Zahlen a ∈ {2, n-2} als Zeugen vernimmt und true zurückgibt, wenn eine dieser Zahlen bezeugen kann, dass n zusammen­gesetzt ist. Ansonsten gibt die Funktion false zurück, d.h. erkennt n aus Mangel an Beweisen des Gegenteils als Primzahl an.

    

3. Schreiben Sie eine Funktion

   isProbablyPrime(n)

   die den Miller-Rabin-Primzahltest mit k=10 durchführt und true zurückgibt, falls n nicht als zusammen­gesetzt entlarvt werden kann.

    

4. Programmieren Sie eine Funktion

   randomPrime(k)

   die eine zufällige Primzahl der Länge k, d.h. zwischen 2^k-1 und 2^k-1 erzeugt.

   Benutzen Sie die Python-Funktion randint(a, b) aus der Bibliothek random zur Erzeugung einer ganzzahligen Zufallszahl zwischen a und b.