HTW Berlin Fachbereich 4 Internationaler Studiengang Internationale Medieninformatik (Bachelor) Aktuelle Themen: Cryptography Winter Term 2024/25

Lab 7: Rechnen mit der CRT-Darstellung

1. Schreiben Sie in Java eine Klasse CRT für das schnelle Potenzieren mit Hilfe des
   chinesischen Restsatzes.
   
   Die Parameter des Konstruktors
   
CRT(BigInteger p, BigInteger q)

sind Primzahlen p ≠ q.
   
   Die Methode
   
   BigInteger pow(BigInteger basis, BigInteger exponent)
   
   soll die modulare Potenz basis^exponent mod n berechnen, wobei n = p·q ist; verwenden Sie dabei das Vorgehen aus §7 des Skripts. Potenzen mod p bzw. qkönnen  Sie dabei mit der Java-Methode modPow berechnen.
   
   
2. Testen sie Ihre Methode pow, indem Sie Ergebnisse mit modPow der Klasse BigInteger vergleichen
   
   
3. Vergleichen Sie die Laufzeit Ihrer Methode pow mit der Laufzeit von modPow:
   
   Erzeugen Sie dazu mit Hilfe der Klasse random in Java mehrfach Zufallszahlen x und y aus der Menge {2, 3, ... n –1}, berechnen Sie xy mod n mit beiden Methoden und mitteln Sie dann die Laufzeiten.
   
   a) Wie groß ist das Verhältnis der Laufzeiten?
   b) Wie hängt Ihr Ergebnis in a) von der Bitlänge von p und q ab?
   c) Was ergibt sich in a), wenn der Exponent klein ist (beispielsweise exponent = 3)?