Lattice Reduction Algorithms: Dynamics, Probabilities, Experiments, Applications. – LAREDA

Lattice reduction algorithms (denoted by LaRedA) (notably the LLL algorithm, created by Lenstra, Lenstra and Lovasz in 1982) aim at finding a ''reduced'' basis of a Euclidean lattice, formed with vectors that are almost orthogonal and short enough. These algorithms play a primary rôle in many areas of mathematics and computer science: cryptology, computer algebra, discrete geometry, and number theory. However, their general behaviour is far from being well understood: many experimental observations (regarding the execution of the algorithms or the geometry of their ouputs), already done by members of the project, pose challenging questions that remain unanswered and lead to natural conjectures which are not proven. - - The project is devoted to a better understanding of these algorithms. This should 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. One of the main motivations for this project is due to the importance, and the variety of applications of LaRedA. We first hope to apply our results for providing a general algorithmic strategy in lattice reduction. We then propose to focus on some particular application areas: cryptology, arithmetics, discrete geometry, in which the project members are specialists, with a particular focus on cryptology. This is an important objective of the project. - - This project is a difficult task, for which many different and complementary approaches must be used. - This is the key point of our project that makes it more powerful than previous unsuccessful attempts. - We propose to adopt three points of view --dedicated modelling, probabilistic aproach and dynamical approach--. This mixed approach has already proved fruitful for small dimensions (the Euclidean algorithms for n= 1, and the Gauss algorithm for n= 2). These small dimensions constitute an important step in the project, since the LLL algorithm can be viewed as a sequence of Gauss reductions on various sublattices of the large lattice. - A-- Dedicated modelling. First, we will define realistic probabilistic models, addressing the various applications of lattice reduction. For each particular area, there are special types of input lattice bases which are used, and this leads to different probabilistic models, that may vary according to the application. Then, we will undertake an analysis of the lattice reduction algorithms, under such probabilistic models: we shall quantify the behaviour of the main parameters which are characteristic of the algorithms, for instance, the number of iterations, the geometry of reduced bases, the evolution of densities during an execution, ... - B-- Probabilistic approach. This line of investigation (already adopted by participants in the project) has led to tangible results in the (somewhat unrealistic) models, where vectors of the input basis are independently chosen according to a distribution that is invariant by rotation. In this way, the following question has been answered: what is the probability for such a basis to be already reduced? We wish to extend this study to the case of realistic models. Furthermore, we plan to study the algorithm itself, not just its input distribution. Whenever an exact computation is not possible, we hope to extract, from the algorithmic structure, some probabilistic properties (martingales, independence, association) enabling an asymptotic study.C-- Dynamical approach. Thanks to earlier results of participants in the project, the dynamics of Euclid's algorithm is now well-understood and there exist many results on the probabilistic behaviour of that algorithm which are obtained by using dynamical systems theory [DS] and related tools, like transfer operators. These techniques are extended to n= 2 (Gauss' algorithm). Lattice reduction algorithms can be viewed as multidime...