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.
Homepage