Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Hauptseminar im SS 2004:
Kryptographische Algorithmen

Themen und Literatur

Literatur: [CP] Crandall, R:, Pommerance, C.Prime Numbers - A computational approach, Springer-Verlag, Berlin, 2001.

1. Primzahltests (siehe auch z.B. The prime pages)
   
   • Siebmethoden für Primzahltests und Faktorisierung. Literatur: [CP] 113 - 150
   • Primes is in P (WWW)
   • (n + 1)-Test für Fermat-Zahlen
   • (n - 1)-Test für Mersenne-Zahlen.

2. Faktorisierung (siehe auch z.B. FactorWorld!)
   
   
   • Pollard rho und p-1 Methode
   • Quadratisches Sieb (QS)
   • Zahlenkörper Sieb (NFS)
   • Diskrete Logarithmen, Faktorisierung mit quadratischen Formen

3. Primzahltests und Faktorisierung mit elliptischen Kurven
   
   • Arithmetik von elliptischen Kurven
   • Faktorisieren mit elliptischen Kurven (ECM)
   • Primzahltests mit elliptischen Kurven
   • Variationen von ECM, EC und diskrete Logarithmen

4. Zahlentheoretische Algorithmen
   
   • GGT, Exponentiation, Modulare Arithmetik
   • Multiplikation großer Zahlen (FFT, DWT)

---

Thomas Bayer, February/12/2004.