Lareda
Lattice Reduction Algorithms: Dynamics, Probabilities, Experiments, Applications
Description of the project
Lattice reductions algorithms aim at finding a "reduced" basis of a Euclidian lattice, formed with vectors
almost orthogonal and short enough. These algorithms - notably the LLL algorithm, created by Lenstra, Lenstra
and Lovasz in 1982 - play a primary role in many areas of mathematics and computer science, like cryptology,
computer algebra, integer linear programming, and number theory. However, their general behaviour is far from beeing
well understood: many experimental observations (regarding the execution of the algorithms or the geometry of the
outputs), already performed by members of the project, pose challenging questions that remain unanswered and
lead to natural conjectures which are yet to be proved.
The project is devoted to a better understanding of these algorithms. This sould lead to a proven explanation
of many of the observed experimental facts, and it conditions improvements of the major algorithms implementing
the lattice reduction process, in the several areas cited. On of the main motivations for this project owes to
the importance and the variety of applications of lattice reduction algorithms. We first hope to apply our results
and provide a general algorithmic strategy in lattice reductions. We then propose to focus on some particular
application areas, namely cryptology, arithmetics and discrete geometry, of which the project members are specialists,
with a particular focus on cryptology. The applications viewpoint is an important objective of the project.
This project represents a difficult task, for which many different and complementary approaches must be used. We
propose to adopt a general methodology which puts together and mixes three different points of view:
dedicated modelling, probabilistic approach, dynamical approach
