Genealogy of lattice reduction : algorithmic description and dynamical analyses (Natural extension of arithmetic algorithms and S-adic system)

Abstract

The present study describes the main algorithms devoted to solving the lattice reduction problem. This is a central algorithmic problem, due to its intrinsic theoretical interest, together to its multiple possible applications, located at many various areas in the interface between mathematics and computer science : computational number theory, integer programming but also complexity theory and cryptology. We first describe the algorithms themselves, inside their genealogy, and explain how the main ideas of small dimensions are used in higher dimensions. We are mainly interested in their probabilistic analysis, and wish to describe in a probabilistic way the main properties of their execution or the geometry of their outputs. Finally, the methodology that conducts these analyses is itself a main subject of interest, as it involves an original mixing between probabilistic modelling of the inputs, analytic combinatorics, and also tools that come from dynamical systems. This method, called dynamical analysis, is completely fruitful in small dimensions, and well explains the transition between the two smaller dimensions. For higher dimensions, such a direct approach is no longer possible, but it can be adapted via the introduction of simplified models.