An LLL-reduction algorithm with quasi-linear time complexity

Andrew Novocin 1, 2 Damien Stehlé 1, 2 Gilles Villard 1, 2
1 LIP - Laboratoire de l'Informatique du Parallélisme
2 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We devise an algorithm, L1 tilde, with the following specifications: It takes as input an arbitrary basis B=(b_i)_i in Z^{d x d} of a Euclidean lattice L; It computes a basis of L which is reduced for a mild modification of the Lenstra-Lenstra-Lovász reduction; It terminates in time O(d^{5+eps} beta + d^{omega+1+eps} beta^{1+eps}) where beta = log max ||b_i|| (for any eps > 0 and omega is a valid exponent for matrix multiplication). This is the first LLL-reducing algorithm with a time complexity that is quasi-linear in the bit-length beta of the entries and polynomial in the dimension d. The backbone structure of L1 tilde is able to mimic the Knuth-Schönhage fast gcd algorithm thanks to a combination of cutting-edge ingredients. First the bit-size of our lattice bases can be decreased via truncations whose validity are backed by recent numerical stability results on the QR matrix factorization. Also we establish a new framework for analyzing unimodular transformation matrices which reduce shifts of reduced bases, this includes bit-size control and new perturbation tools. We illustrate the power of this framework by generating a family of reduction algorithms.
Keywords : lattice basis reduction LLL computational complexity bit complexity
Type de document :
Communication dans un congrès
STOC'11 - 43rd annual ACM symposium on Theory of computing, 2011, San Jose, United States. ACM New York, NY, USA, pp.403-412, 2011, 〈10.1145/1993636.1993691〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00534899
Contributeur : Gilles Villard <>
Soumis le : jeudi 7 avril 2011 - 16:13:04
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : jeudi 30 mars 2017 - 09:17:19

Fichier

L1-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

ENS-LYON | INRIA | LIP | UNIV-LYON1

Citation

Andrew Novocin, Damien Stehlé, Gilles Villard. An LLL-reduction algorithm with quasi-linear time complexity. STOC'11 - 43rd annual ACM symposium on Theory of computing, 2011, San Jose, United States. ACM New York, NY, USA, pp.403-412, 2011, 〈10.1145/1993636.1993691〉. 〈ensl-00534899v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

1028

Téléchargements de fichiers

1104

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD