Proseminar
Das Proseminar ist aktuell voll. Weitere Informationen erhalten akzeptierte Teilnehmer über KOALA.
Wir werden ausgewählte Themen rund um Primzahlen behandeln. So werden wir Verfahren kennenlernen, welche testen, ob eine Zahl eine Primzahl ist. Am Ende werden wir auch sehr einfache Algorithmen vorstellen, die Zahlen faktorisieren.
Themen
1. Vortrag: Zahldarstellungen, Binärzahlen, rechnen mit Binärzahlen, russische Bauernmultiplikation
2. Vortrag: Chinesischer Restsatz, kleiner Fermatscher Satz
3. Vortag: Schnelles Potenzieren, rekursive Folgen wie z.B. Fibonacci-Zahlen
4. Vortrag: Zyklische Gruppen, Primitivwurzeln modulo p
5. Vortrag: Zufallszahlengeneratoren
6. Vortrag: Schwache Pseudoprimzahlen und Carmichael-Zahlen
7. Vortrag: Eulersche Phi-Funktion
8. Vortrag: Kryptographie (RSA)
9. Vortrag: Quadratische Reste, Legendre-Symbol, Jacobi-Symbol und Berechnung (ohne Beweisdes Reziprozitätsgesetzes für das Legendre-Symbol, ohne Beweis des zweiten Ergänzungssatzes)
10. Vortrag: Beweis des zweiten Ergänzungssatzes und des quadratischen Reziprozitätsgesetz fürdas Legendre-Symbol
11. Vortrag: Primzahl-Test nach Solovay-Strassen (siehe auch: Eric Bach)
12. Vortrag: Primzahl-Test nach Miller-Rabin (siehe auch: Eric Bach)
13. Vortag: Faktorisierung mit der Pollard-Rho-Methode
14. Vortrag: Berechnung des diskreten Logarithmus (Forster, Kap. 21 bis Ende Abschnitt 21.7)
15. Vortag: Faktorisierung mit der (p-1)-Methode
16. Vortrag: Konstruktion von quadratischen Körpererweiterungen
17. Vortrag: Mersenne-Zahlen und Lucas-Lehmer-Test
18. Vortrag: Faktorisierung mit der (p+1)-Methode
19. Vortrag: Faktorisierung mit elliptischen Kurven
20. Vortrag: Quadratisches Sieb
Literatur
Otto Forster: Algorithmische Zahlentheorie, (2. Auflage von 2015)
Müller-Stach: Elementare und algebraische Zahlentheorie
Eric Bach: Algorithmic Number Theory in Auszügen bei google books.
Hinweis zur Nutzung der digitalen Quellen:
Um berechtigt zu sein, die hier angegebenen Links für die Downloads zu nutzen, muss man sich über die Universität einloggen.
Dies ist beispielsweise der Fall, wenn Sie mit Ihrem Notebook via wlan in der Uni (eduroam oder webauth) im Internet sind. Von zu Hause aus klappt das nur, wenn Sie vpn installiert haben.
Beachten Sie hierzu die Seiten: