| Article Id: |
 |
ensl-00534899, version 2 |
|
|
| Domaine: |
|
|
|
|
| Titre: |
|
An LLL-reduction algorithm with quasi-linear time complexity |
|
|
| Auteur(s): |
|
Andrew Novocin1, 2, Damien Stehlé1, 2, Gilles Villard1, 2 |
|
|
| Laboratoire: |
|
| 1: |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 2: |
Inria Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme - ARENAIRE |
|
|
|
| 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 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. |
|
|
|
Langue du texte
intégral: |
|
English |
|
|
| Mots-clés: |
|
lattice basis reduction – LLL – computational complexity – bit complexity |
|
|
Export this paper
