Forster: Algorithmic Number Theory

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

Example Code

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.

Detailed Contents

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

Otto Forster (), 2002-01-28/2002-05-02