The goal of this class is to review three important questions in
algorithmic number theory: primality testing, the discrete logarithm
problem in **GF**(p^{n})^{*}, 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:

*Math/Computer algebra prerequisites*: fast arithmetic, finite fields, ...*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.*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^{n})^{*}, p small*Algorithms for lattices*- Definitions, basic algorithmic problems

- The LLL lattice basis reduction algorithm

- Babai algorithm, Kannan's embedding for CVP

- Some applications