Skip to Content

ANR Blanche

Catégorie : 
ANR
Titre du Projet-Contrat-ANR : 
LAREDA : Lattice Reduction Algorithms : Dynamics, Probabilities, Experiments, Applications
Année : 
2007
Descriptif : 

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.

Porteur de projet au GREYC : 

Brigitte Vallée (coordinatrice)

Entreprises & partenaires : 
  • LIMM Montpellier
  • IRISA
  • LIP LYON
  • IMB DIJON