Proseminar Primzahlen - Sommersemester 2010

Aktuelle Termine

Das Proseminar findet voraussichtlich im SS 2010 immer donnerstags von 16-20 Uhr statt. Es gibt eine erste vorläufige Planung der Termine. Neben den beiden Feiertagen habe ich den 17.6.2010 und den 22.7.2010 freigelassen. Dies könnte sich noch ändern.

Bitte beachten Sie, dass das Seminar in der ersten Semesterwoche startet und wir mit jeweils 2 Vorträgen anfangen. So kommt man vielleicht früher dran als erwartet.

Thema

Wie kann man effizient entscheiden, ob eine Zahl eine Primzahl ist? Wir werden in diesem Seminar einige einfache Methoden kennen lernen, um zu testen, ob eine Zahl eine Primzahl ist. Weiterhin werden wir zwei der einfachsten Faktorisierungsalgorithmen vorstellen.

Im Jahr 2002 überraschten drei Inder die mathematische Welt mit einem neuen deterministischem Primzahltest, der in Polynomzeit testet, ob eine Zahl eine Primzahl ist. Dieses Ereignis wurde weltweilt in mehreren großen Zeitungen veröffentlicht. Der Beweis dieses neuen Algorithmus ist überraschend einfach und wir werden ihn in den letzten beiden Vorträgen vorstellen.

Übersichtsartikel von Folkmar Bornemann

AKS auf der Wikipedia

Wie halte ich einen Seminarvortrag?

Scheinerwerb

Vorträge

1.     Kleiner Fermat, Chinesischer Restsatz

Inhalt:                 [MP] Kap. 4, [BRK] Kap. 2.8, 3.1

Vortragende:    H. Eisenhofer                         Datum: 15.04.2010         Uhrzeit: 16:00 Uhr

2.     Schwacher Pseudoprimzahltest, Carmichaelzahlen, Schnelles Potenzieren

Inhalt:                 [MP] Def. 11.8, Kor. 11.10, [BRK] Kap. 4.1-4.3, [GG] Kap. 4.3, 18.2, [BS] Kap. 9.3

Vortragende:    A. Fahle                                  Datum: 15.04.2010         Uhrzeit: 18:00 Uhr

3.     Teilertheorie / Euklidische Ringe

Inhalt:                 Ausschnitte aus [MP], Kap. 2

Vortragender:   M. Damschen                        Datum: 22.04.2010         Uhrzeit: 16:00 Uhr

4.     Zyklische Gruppen und Primitivwurzeln

Inhalt:                 [MP] Kap. 7 bis Lemma 7.4, [BRK] Kap. 3.2, 3.3, (3.8)

Vortragender:   M. Feldmann                          Datum: 22.04.2010         Uhrzeit: 18:00 Uhr

5.     Eulersche φ–Funktion und Kryptographie

Inhalt:                 [MP] Kap. 5, [BRK] Kap. 2.9, 4.7, [GG] Kap. 20.2-20.3

Vortragende:    J. Hagemann, E. Herzog      Datum: 29.04.2010         Uhrzeit: 16:00 Uhr

6.     Quadratische Reste, Legendre-Symbol, Jacobi-Symbol und Berechnung

Inhalt:                 [MP] Kap. 8, außer Beweis von Satz 8.7 und 8.12, [BRK] Kap. 3.4

Vortragende:    O. Ebel, F. Wittrock              Datum: 06.05.2010         Uhrzeit: 16:00 Uhr

7.     Reziprozitätsgesetz

Inhalt:                 [MP] Satz 8.7, 8.12, [BRK] Kap. 3.4

Vortragender:   F. Ahmed                               Datum: 20.05.2010         Uhrzeit: 16:00 Uhr

8.     Summe von 2 und 3 Quadraten

Inhalt:                 [MP] Kap. 9 Anfang

Vortragender:   T. Meier-Hans                        Datum: 27.05.2010         Uhrzeit: 16:00 Uhr

9.     Summe von 4 Quadraten

Inhalt:                 [MP] Kap. 9 Ende

Vortragender:   S. Schulte                               Datum: 27.05.2010         Uhrzeit: 18:00 Uhr

10.       Primzahltest von Solovay-Strassen

Inhalt:                 [MP] Satz 11.12, [BS] Kap. 9.4, 9.5

Vortragender:   O. Schäfer                             Datum: 10.06.2010         Uhrzeit: 16:00 Uhr

11.       Primzahltest von Miller-Rabin (Faktorisierung von Carmichaelzahlen)

Inhalt:                 [MP] Kap. 11.14-11.15, [GG] Kap. 18.3, [BS] Kap. 9.4

Vortragender:   H. Vogelsang                         Datum: 08.07.2010         Uhrzeit: 16:00 Uhr

12.       Mersenne-Primzahlen, Lucas-Lehmer-Test

Inhalt:                 [MP] Satz 11.1, [BRK] Kap. 4.6

Vortragender:   R. Patzer-Meyer                    Datum: 24.06.2010         Uhrzeit: 16:00 Uhr

13.       Der n-1 Test und Fermatsche Primzahlen

Inhalt:                 [MP] Satz 11.3 - Satz 11.6

Vortragender:   D. Frischemeyer                   Datum: 24.06.2010         Uhrzeit: 18:00 Uhr

14.       Pollard ρ-Methode

Inhalt:                 [GG] Kap. 19.4, [CP] Kap. 5.2.1

Vortragende:    A. Celik, M. Nolte                  Datum: 01.07.2010         Uhrzeit: 16:00 Uhr

15.       Pollard (p-1)-Methode

Inhalt:                 [GG] Kap. 19.6, [CP] Kap. 5.4

Vortragende:    P. Schleiter, J.-P. Weber     Datum: 01.07.2010         Uhrzeit: 18:00 Uhr

ACHTUNG: Am 08.07.2010 wird der Vortrag Nr. 11 um 16 Uhr
gehalten!

16.       AKS I

Inhalt:                 Originalartikel, [MP] Kap. 11

Vortragende:   T. Pieper, J. Sallen               Datum: 15.07.2010         Uhrzeit: 16:00 Uhr

17.       AKS II

Inhalt:                 Originalartikel, [MP] Kap. 11

Vortragende:    T. Pieper, J. Sallen               Datum: 15.07.2010         Uhrzeit: 18:00 Uhr

Literatur

Hinweis: Um berechtigt zu sein, den 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:
http://www.ub.uni-paderborn.de/ebibliothek/vpn.shtml
bzw. http://imt.uni-paderborn.de/unser-angebot/dienste-a-z/dienste-nach-themen/vpn/

BS
E. Bach und J. Shallit, Algorithmic Number Theory, Vol.1: Efficient Algorithms, MIT Press, Cambridge MA. 1996.

BRK
A. Bartholome, J. Rung und H. Kern, Zahlentheorie für Einsteiger, Vieweg, 2006.

Co
H. Cohen, A course in computational Algebraic number theory, Springer, Berlin-Heidelberg-New York, GTM 138, 1993.

CP
R. Crandall und C. Pommerance, Prime Numbers, Springer, 2001

Fo
O. Forster, Algorithmische Zahlentheorie, Vieweg, 1996.

GG
J. von zur Gathen and J. Gerhard, Modern Computer Algebra. Cambridge University Press, 1999.

MP
S. Müller-Stach und J. Piontkowski, Elementare und algebraische Zahlentheorie. Vieweg, 2006.