The goal of this class is to review three important questions in algorithmic number theory: primality testing, the discrete logarithm problem in GF(pⁿ)^*, 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
   Compositeness testing: Fermat, Dubois-Selfridge-Miller-Rabin
   Group-based primality testing I: N-1, N+1. Application to Mersenne primes
   Group-based primality testing II: Elliptic curves based primality testing: Goldwasser-Killian, ECPP.
   Primes is in P: the AKS primality test.
3. Discrete logarithms
   Definition, applications in cryptology
   Exponential-time methods: Pollard rho, baby step giant step
   Pohlig-Hellman method
   Interlude: sparse linear algebra
   Subexponential (L(1/2)) methods for GF(q)^*
   Quasi-polynomial method for GF(pⁿ)^*, p small
4. Algorithms for lattices
   Definitions, basic algorithmic problems
   The LLL lattice basis reduction algorithm
   Babai algorithm, Kannan's embedding for CVP
   Some applications