An LLL-reduction algorithm with quasi-linear time complexity - ENS de Lyon - École normale supérieure de Lyon Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2010

An LLL-reduction algorithm with quasi-linear time complexity

Résumé

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 innovative 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.
Fichier principal
Vignette du fichier
L1-hal.pdf (273.72 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

ensl-00534899 , version 1 (10-11-2010)
ensl-00534899 , version 2 (07-04-2011)

Identifiants

  • HAL Id : ensl-00534899 , version 1

Citer

Andrew Novocin, Damien Stehlé, Gilles Villard. An LLL-reduction algorithm with quasi-linear time complexity. 2010. ⟨ensl-00534899v1⟩
755 Consultations
2439 Téléchargements

Partager

Gmail Facebook X LinkedIn More