Vorlesung «Algorithmen für Zahlen und Primzahlen» (2V)

Prof. Dr. Hans-Gert Gräbe

Allgemeines

Anrechenbar:

• für Studenten im Studiengang Master Informatik im Modul 10–202-2110 “Algorithmische Strukturen in Algebra und Logik”
• für Studenten im Studiengang Diplom-Mathematik im Modul “Computational Algebra” 10-MATHD-5104 oder im Nebenfach Informatik
• für Studenten im Lehramt Mathematik (im “Wahlpflichtplatzhalter aus Algebra und Geometrie”)
• für Studenten der Informatik im Nebenfach Mathematik

Übersicht

In der Vorlesung werden die wichtigsten algorithmischen Ideen, die sich um den Begriff der Teilbarkeit, Primzahleigenschaft und Faktorisierung ganzer Zahlen gruppieren, vorgestellt. Die Vorlesung orientiert sich am Buch [Crandall, Pomerance 01] und berührt im Einzelnen die folgenden Themen:

• Langzahldarstellung ganzer Zahlen
• Schnelle Arithmetik ganzer Zahlen
• Klassische Primzahltests
• Moderne Primzahltests
• Primzahlzertifikate
• Faktorisierung ganzer Zahlen

Literatur

• D. Bressoud, S. Wagon: Computational Number Theory. Key College Publishing and Springer, New York 2000.
• R. Crandall, C. Pomerance: Prime Numbers – A Computational Perspective. Springer, New York 2001.
• D.E. Knuth: The art of computer programming. Vol. 2: Seminumerical algorithms. Addison Wesley 1981.
• P. Ribenboim: The new book of prime number records. Springer, New York 1996.
• G. Tenenbaum: The Prime Numbers and Their Distribution. AMS Student Mathematical Library, vol. 6, 2001.

Erwartete Vorkenntnisse

Gute Kenntnisse der linearen Algebra, Grundkenntnisse der höheren Algebra.

Anrechnung der Leistung

Zur Vorlesung wird eine mündliche Prüfung angeboten.