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

Xiao-Wen Chang, Damien Stehlé and Gilles Villard

Abstract: In 1982, Arjen Lenstra, Hendrik Lenstra Jr. and Laszló 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. In order to circumvent the use of rational/exact arithmetic with large bit-sizes, it is tempting to consider using floating-point arithmetic with small precision to compute 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 are very useful to devise LLL-type algorithms relying on floating-point approximations.

Download: pdf.

Additional material: Maple worksheet.