Analyses de l'algorithme de Gauss. Applications à l'analyse de l'algorithme LLL.
Vera, Antonio · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
This thesis is dedicated to the probabilistic analysis of algorithms to reduce Euclidean networks. Euclidean network is all coefficients of linear combinations of a base integers (b_1, ..., b_n) \ subset R ^ n. The reduction of a network is to find a base formed of relatively short and relatively orthogonal vectors from a data base input. The famous LLL algorithm solves this problem efficiently in arbitrary dimension. It is widely used, but poorly understood. We focus on the analysis in the case n = 2, where LLL is the Gauss membership, as it is a building block for the case n> = 3, we analyze precisely the Gauss, both in of its execution (number of iterations, bit complexity, cost "additives") that the geometry of the output data (default Hermite first minimum and second minimum orthogonalized). We work in a very general probabilistic model for studying both easier than the difficult instances instances. This model allowed us to study the transition to the Euclidean algorithm, which corresponds to the case where the vectors of the input base are collinear. We use dynamic methods: algorithms are seen as dynamic systems, and generating functions involved are expressed in terms of the transfer operator. These highly accurate results in 2D are a first step in the analysis of the LLL algorithm in the general case.