## Lattice Reduction

Lattice reduction is a powerful tool to find short vectors in lattices. Mostly known in this area is the so-called LLL algorithm of Lenstra, Lenstra and Lovasz. Roughly speaking, given a basis of a lattice, the LLL algorithm outputs a reduced basis for the same lattice, with the difference that this reduced basis has plenty of advantages and many applications in number theory and in cryptography.

A first goal of this project would be to understand reduced bases from an algorithmic point of view, and test various examples. In a second time, one could use the LLL algorithm as a black-box (there are many good implementations of the algorithm in various languages) to study some of its applications such as

- approximating numbers by fractions with small numerator and denominator. A related application is simultaneous Diophantine approximation.
- finding small integer roots of univariate polynomials modulo a given integer. Via lattice reduction (LLL) one can find such a root by finding a polynomial that has the same zeroes as the target polynomial but has smaller coefficients. This is known as the Coppersmith technique, after Don Coppersmith.
- many other applications

A more detailed description of the project is available here.

**Schedule:** Winter semester 2018/2019

**Difficulty level:**
EML 2 (especially for students in their 3rd semester).