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
Journal articles

Perturbation Analysis of the QR Factor R in the Context of LLL Lattice Basis Reduction

Xiao-Wen Chang Damien Stehlé 1, 2, * Gilles Villard 1, 2, *
* Corresponding author
2 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In 1982, Arjen Lenstra, Hendrik Lenstra Jr. and László Lovász introduced an efficiently computable notion of reduction of basis of a Euclidean lattice that is now commonly referred to as LLL-reduction. The precise definition involves the R-factor of the QR factorisation of the basis matrix. A natural mean of speeding up the LLL reduction algorithm is to use a (floating-point) approximation to the R-factor. In the present article, we investigate the accuracy of the factor R of the QR factorisation of an LLL-reduced basis. Our main contribution is the first fully rigorous perturbation analysis of the R-factor of LLL-reduced matrices under column-wise perturbations. Our results should be very useful to devise LLL-type algorithms relying on floating-point approximations.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00529425
Contributor : Gilles Villard Connect in order to contact the contributor
Submitted on : Thursday, April 7, 2011 - 4:28:46 PM
Last modification on : Friday, February 4, 2022 - 3:15:57 AM
Long-term archiving on: : Friday, July 8, 2011 - 2:38:04 AM

File

qrperturb2011.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00529425, version 2

Collections

Citation

Xiao-Wen Chang, Damien Stehlé, Gilles Villard. Perturbation Analysis of the QR Factor R in the Context of LLL Lattice Basis Reduction. Mathematics of Computation, American Mathematical Society, 2012, 81 (279), pp.1487-1511. ⟨ensl-00529425v2⟩

Share

Metrics

Record views

400

Files downloads

283