HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

An LLL-reduction algorithm with quasi-linear time complexity

Andrew Novocin 1, 2 Damien Stehlé 1, 2 Gilles Villard 1, 2
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.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00534899
Contributor : Gilles Villard Connect in order to contact the contributor
Submitted on : Thursday, April 7, 2011 - 4:13:04 PM
Last modification on : Friday, February 4, 2022 - 3:18:57 AM
Long-term archiving on: : Thursday, March 30, 2017 - 9:17:19 AM

File

L1-hal.pdf
Files produced by the author(s)

Identifiers

Collections

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. pp.403-412, ⟨10.1145/1993636.1993691⟩. ⟨ensl-00534899v2⟩

Share

Metrics

Record views

674

Files downloads

2121