Algorithmen für Zahlen und Primzahlen

Zur Vorlesung gibt es ein Skript aus dem Jahr 2003. Die Vorlesung orientiert sich am Buch [Crandall, Pomerance 01].

Kenntnisse über das Rechnen mit Resten werden vorausgesetzt. Ein entsprechendes Studienmaterial gibt noch einmal einen Überblick über grundlegende Zusammenhänge. Auch in der ersten Übung wird auf dieses Thema noch einmal eingegangen.

Zur Vorlesung erscheinen wöchentlich Übungsaufgaben, deren Bearbeitung fakultativ ist. In etwa 14-täglichem Rhythmus biete ich eine Konsultation an, wo die Übungsaufgaben besprochen werden.

Für die Übungsaufgaben ist die Verwendung eines Computeralgebra-Systems (CAS) zu empfehlen.

Mu PAD- Home Use- Lizenz anfordern: http://www.informatik.uni-leipzig.de/~graebe/ComputerAlgebra/mupad-lizenz.html

Zur Vorlesung findet am 05.02.2007 eine mündliche Modulprüfung statt.

Weitere Interessenten melden sich bitte bis zum 21.01. per email bei mir an.

Vorlesungstermine und -inhalte

17.10.: Einleitung. Primzahlen – grundlegende Eigenschaften

• gcd und lcm 
• Euklidscher Algorithmus
• Zur Verteilung der Primzahlen
• Die Primzahldichtefunktion

24.10.: Rechnen mit ganzen Zahlen I

• Ein- und Ausgabeoperationen, Addition, Multiplikation

31.10: Feiertag

07.11.: Rechnen mit ganzen Zahlen II

• Division mit Rest, gcd-Berechnung und Euklidscher Algorithmus
• Rechnen mit Resten. Zahlentheoretische Vorbereitungen.

14.11.: Zahlentheoretische Vorbereitungen

• Der Chinesische Restklassensatz
• Die Gruppe der primen Restklassen
• Die Sätze von Euler und Carmichael

21.11.: Zahlentheoretische Vorbereitungen

• Rechnen in endlichen Körpern
• Trial Division
• Das Sieb des Eratostenes
• Der Fermat-Test und seine Las-Vegas-Variante

28.11.: Primtest-Verfahren

• Carmichael-Zahlen
• Der Rabin-Miller-Test
• Rabin-Miller-Zeugen und mögliche deterministische Primzahl-Tests mit polynomialer Laufzeit

05.12.: Primtest-Verfahren

• Der Solovay-Strassen-Test
• Primzahl-Zertifikate

12.12.: Primtest-Verfahren

• Der deterministische Primzahltest von Agrawal, Kayal und Saxena

19.12.: Faktorisierung ganzer Zahlen

• Der deterministische Primzahltest von Agrawal, Kayal und Saxena
• Das Faktorisierungs-Gerüst

09.01.: Faktorisierung ganzer Zahlen

• trialFactor – Faktorisierung durch Probedivision
• Faktorisierungsmethoden – ein Überblick
• Die Fermat-Methode und Lehman Factor

16.01.: Faktorisierung ganzer Zahlen

• Pollards Rho-Methode

23.01.: Faktorisierung ganzer Zahlen

• Das quadratische Sieb
• Pollards (p-1)-Methode

30.01.: Mersennesche Zahlen

• Das Cunningham-Projekt

Prüfung

Ort: Johannisgasse 26, Raum 5–18. Beisitzer: Frank Schumacher