Algorithmic Number Theory

Lecturer: Guillaume Hanrot

The goal of this class is to review three important questions in algorithmic number theory: primality testing, the discrete logarithm problem in GF(pn)*, and algorithms for lattices.

The first of these topics has come to a satisfactory solution in theory and in practice, while on the contrary the last two have developed at a fast pace over the last 5 years.

Outline of the class:

  1. Math/Computer algebra prerequisites: fast arithmetic, finite fields, ...
  2. Primality testing
  3. Discrete logarithms
  4. Algorithms for lattices
Prerequisites: Good knowledge of the rings Z/nZ. Though the fist class will be devoted to this, a basic knowledge of computer algebra (fast arithmetic, gcd computations) is preferable.