## Forster: Algorithmic Number Theory

Course (4 hours weekly + 2 hours Problem sessions) by O. Forster
Summer Semester 2002, Department of Mathematics, LMU München

Time and Room: Tue, Fri 9-11, E 6
Starts on Tuesday, April 18, 2002, at 9:15h

Problem sessions: Tue 14-16, HS 138

Contents: In this course we will give an introduction to number theory from the elements up to the quadratic reciprocity law with an emphasis on algorithmic methods. Important problems (which have applications in modern cryptography) are the factorization of integers, recognition of primes and calculation of discrete logarithms. Algorithmic number theory has a long history (Eucidean algorithm, sieve of Eratosthenes). With the advent of computers, new and efficient algorithms have been found. Some of them use interesting algebraic and geometric methods, like the theory of Elliptic Curves. Besides algorithms for integers, we will study in the course also algorithms for polynomials, in particular over finite fields.

Prerequisites: Familiarity with basic concepts of algebra (groups, rings, ideals, fields, polynomials) is assumed. Some programming experience is useful.

For: Students of the International Master Program in Mathematics,
StudentInnen mit Studienziel Mathematik-Diplom und Lehramt nach Vordiplom bzw. Zwischenprüfung

Literature

• E. Bach and J. Shallit: Algorithmic Number Theory, Vol. I. MIT Press
• H. Cohen: A Course in Computational Algebraic Number Theory. Springer-Verlag
• O. Forster: Algorithmische Zahlentheorie, Vieweg-Verlag
• P. Giblin: Primes and Programming. An Introduction to Number Theory with Computing. Cambridge UP
• D. Knuth: The Art of Computer Programming, Vol 2. Seminumerical algorithms. Addison-Wiley
• H. Riesel: Prime Numbers and Computer Methods for Factorization. Birkhäuser

This course will be followed in WS 2002/03 by a course in Cryptography and a Seminar on Algorithmic Number Theory and Cryptography
Topics for master theses (and diploma theses) will be available from these subjects.
Otto Forster (), 2002-01-28/2002-05-02