Brigitte Vallée ; Antonio Vera - Lattice reduction in two dimensions: analyses under realistic probabilistic models

dmtcs:3549 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3549
Lattice reduction in two dimensions: analyses under realistic probabilistic modelsArticle

Authors: Brigitte Vallée 1; Antonio Vera 1

  • 1 Equipe AMACC - Laboratoire GREYC - UMR6072

The Gaussian algorithm for lattice reduction in dimension 2 is precisely analysed under a class of realistic probabilistic models, which are of interest when applying the Gauss algorithm "inside'' the LLL algorithm. The proofs deal with the underlying dynamical systems and transfer operators. All the main parameters are studied: execution parameters which describe the behaviour of the algorithm itself as well as output parameters, which describe the geometry of reduced bases.


Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Section: Proceedings
Published on: January 1, 2007
Imported on: May 10, 2017
Keywords: Euclid's algorithm,LLL algorithm,Gauss' algorithm,Lattice Reduction,probabilistic analysis of algorithms,Dynamical Systems,Dynamical analysis of Algorithms.,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

3 Documents citing this article

Consultation statistics

This page has been seen 164 times.
This article's PDF has been downloaded 191 times.