LLL reducing with the most significant bits

Abstract : Let B be a basis of a Euclidean lattice, and \tilde{B} an approximation thereof. We give a sufficient condition on the closeness between \tilde{B} and B so that an LLL-reducing transformation U for \tilde{B} remains valid for B. Further, we analyse an efficient reduction algorithm when B is itself a small deformation of an LLL-reduced basis. Applications include speeding-up reduction by keeping only the most significant bits of B, reducing a basis that is only approximately known, and effi- ciently batching LLL reductions for closely related inputs.
Type de document :
Communication dans un congrès
ISSAC'14, International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. 2014, 〈10.1145/2608628.2608645〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00993445
Contributeur : Gilles Villard <>
Soumis le : lundi 5 septembre 2016 - 08:50:21
Dernière modification le : mardi 13 novembre 2018 - 18:12:49
Document(s) archivé(s) le : mardi 6 décembre 2016 - 12:59:06

Fichier

lift.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Goel Sarushi, Ivan Morel, Damien Stehlé, Gilles Villard. LLL reducing with the most significant bits. ISSAC'14, International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. 2014, 〈10.1145/2608628.2608645〉. 〈ensl-00993445〉

Partager

Métriques

Consultations de la notice

586

Téléchargements de fichiers

107