Prosem­in­ar

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.

 

The­men

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

Lit­er­at­ur

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:

imt.uni-paderborn.de/vpn-zugang/