Some numerical considerations for lattice basis reduction - ENS de Lyon - École normale supérieure de Lyon Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Some numerical considerations for lattice basis reduction

Résumé

Fastest algorithms and implementations for LLL basis reduction are highly hybrid symbolic-numeric. A "numerical engine" computes, via a orthogonalization process, the unimodular transformations that will improve the quality of the basis. Then, for example in the case of integer lattice bases, the transformations are applied in exact arithmetic. We focus on several aspects concerning the choice of the precision than can be used for the numerical computations. We present theoretical bounds based on reducedness perturbation results, and on a "fully numerical view" of the algorithms. This leads to new methods for certifying reducedness. We also adopt a practical point of view for looking at approches with a dynamical tuning of the precision, and at the difficulties for heuristically mastering the behavior of the codes when the precision is very low compared to theoretical requirements.
Fichier non déposé

Dates et versions

ensl-00994751 , version 1 (22-05-2014)

Identifiants

  • HAL Id : ensl-00994751 , version 1

Citer

Gilles Villard. Some numerical considerations for lattice basis reduction. Fields Institute Workshop on Hybrid Methodologies for Symbolic-Numeric Computation, Nov 2011, David R. Cheriton School of Computer Science, Waterloo, Ontario, Canada. ⟨ensl-00994751⟩
57 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More