Algorithmen für Zahlen und Primzahlen

Dateien zu dieser Seite

serie1.pdf Termin: 24.10.

serie10.pdf Termin 23.1. letzte Serie

serie2.pdf Termin 7.11.

serie3.pdf Termin 14.11.

serie4.pdf Termin 21.11.

serie5.pdf Termin 28.11.

serie6.pdf Termin 5.12.

serie7.pdf Termin 12.12.

serie8.pdf Termin 19.12.

serie9.pdf Termin 16.1.


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 PDF DocumentStudienmaterial 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

Prüfung


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


05.02.0714:00-14:20 8963070
05.02.0714:30-14:50 9160500


 
Zu dieser Seite gibt es 10 Dateien. [Zeige Dateien/Upload]
Kein Kommentar. [Zeige Kommentare]