O. Forster: Algorithmische Zahlentheorie

Fortbildungsveranstaltung für Mathematiklehrerinnen und Mathematiklehrer im SS 1999
am Mathematischen Institut der LMU München
Theresienstr. 39, Hörsaal E4

Die Veranstaltung findet 14-täglich Di 16-18 Uhr statt.

Termine
4. und 18. Mai,
8. und 22. Juni,
6. und 13. Juli 1999.

Beschreibung: Die Algorithmische Zahlentheorie hat eine lange Geschichte. Zwei der ältesten Algorithmen der Mathematik, der Euklidische Algorithmus und das Sieb des Erathostenes, gehören zur Zahlentheorie. Auch Fermat, Lagrange, Gauß und andere Mathematiker entwickelten zahlentheoretische Algorithmen. Die meisten der klassischen Algorithmen, die ursprünglich für manuelle Rechnungen konzipiert waren, haben sich auch für den Gebrauch durch den Computer bewährt.

In den letzten Jahren sind viele neue Verfahren entwickelt worden (z.B. für Primzahltests oder für die Faktor-Zerlegung großer ganzer Zahlen), an die man früher wegen des Umfangs der damit verbundenen Rechnungen nicht denken konnte. Das heutige Interesse an zahlentheoretischen Algorithmen ist u.a. durch ihre Anwendungen in den zur Sicherung des elektronischen Datenverkehrs benutzten Public Key Kryptographie-Verfahren begründet. Das RSA-Verfahren ist das bekannteste Beispiel dafür.

In der Vorlesung sollen einige der wichtigsten Algorithmen und ihre Anwendungen vorgestellt werden. Natürlich kommen auch klassische Themen wie Fibonacci-Zahlen, Fermatsche und Mersennesche Primzahlen, vollkommene Zahlen, und ihre algorithmischen Aspekte zur Sprache. Alle besprochenen Verfahren werden auf dem Computer implementiert (zum Verständnis reichen Grundkenntnisse einer höheren Programmiersprache, wie Pascal oder C). Das (wohl auch für Schüler) Attraktive an der Algorithmischen Zahlentheorie ist, dass man es meist mit Aussagen über natürliche Zahlen zu tun hat, die einfach zu formulieren sind (wenn auch nicht immer einfach zu beweisen) und die man mit dem Computer an nicht-trivialen Beispielen nachvollziehen kann.

Inhalt
  1. Die Fibonacci-Zahlen
  2. Der Euklidische Algorithmus
  3. Der Ring Z/m
  4. Quadratische Reste
  5. Fermat'sche und Mersenne'sche Primzahlen
  6. Probabilistische Primzahlteste
  7. Anwendungen in der Kryptographie

Software: Die numerischen Beispiele zur Vorlesung wurden mit dem
Multipräzisions-Interpreter ARIBAS
durchgeführt, der zum freien Download zur Verfügung steht.

Literatur
Forster: Algorithmische Zahlentheorie , Vieweg-Verlag 1996
Bartolomé/Rung/Kern: Zahlentheorie für Einsteiger. Vieweg-Verlag 1995
H. Cohen: A Course in Computational Algebraic Number Theory. Springer-Verlag 1996
Otto Forster (email) 1999-05-12