Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction

Chang, Xiao-Wen; Stehlé, Damien; Villard, Gilles

doi:10.1090/S0025-5718-2012-02545-2

Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction
HTML articles powered by AMS MathViewer

by Xiao-Wen Chang, Damien Stehlé and Gilles Villard PDF

Math. Comp. 81 (2012), 1487-1511 Request permission

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 factorization 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 columnwise perturbations.

Our results are very useful to devise LLL-type algorithms relying on floating-point approximations.

References

Xiao-Wen Chang and Christopher C. Paige, Componentwise perturbation analyses for the $QR$ factorization, Numer. Math. 88 (2001), no. 2, 319–345. MR 1826856, DOI 10.1007/PL00005447
Xiao-Wen Chang, Christopher C. Paige, and G. W. Stewart, Perturbation analyses for the $QR$ factorization, SIAM J. Matrix Anal. Appl. 18 (1997), no. 3, 775–791. MR 1453550, DOI 10.1137/S0895479896297720
X.-W. Chang and D. Stehlé, Rigorous perturbation bounds of some matrix factorizations, SIAM J. Matrix Anal. Appl. 31 (2010), no. 5, 2841–2859. MR 2740636, DOI 10.1137/090778535
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
U. Fincke and M. Pohst, A procedure for determining algebraic integers of given norm, Computer algebra (London, 1983) Lecture Notes in Comput. Sci., vol. 162, Springer, Berlin, 1983, pp. 194–202. MR 774811, DOI 10.1007/3-540-12868-9_{1}03
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
R. Kannan, Improved algorithms for integer programming and related lattice problems, Proceedings of the 15th Symposium on the Theory of Computing (STOC 1983), ACM Press, 1983, pp. 99–108.
Donald E. Knuth, The analysis of algorithms, Actes du Congrès International des Mathématiciens (Nice, 1970) Gauthier-Villars, Paris, 1971, pp. 269–274. MR 0423865
Henrik Koy and Claus Peter Schnorr, Segment LLL-reduction with floating point orthogonalization, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 81–96. MR 1903889, DOI 10.1007/3-540-44670-2_{8}
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
L. Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM Publications, 1986, CBMS-NSF Regional Conference Series in Applied Mathematics.
Ivan Morel, Damien Stehlé, and Gilles Villard, H-LLL: using Householder inside LLL, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 271–278. MR 2742770, DOI 10.1145/1576702.1576740
—, From an LLL-reduced basis to another, Work in progress, 2010.
W. H. Mow, Maximum likelihood sequence estimation from the lattice viewpoint, IEEE Transactions on Information Theory 40 (1994), 1591–1600.
Phong Q. Nguyễn and Damien Stehlé, Floating-point LLL revisited, Advances in cryptology—EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494, Springer, Berlin, 2005, pp. 215–233. MR 2352190, DOI 10.1007/11426639_{1}3
Phong Q. Nguyen and Damien Stehlé, An LLL algorithm with quadratic complexity, SIAM J. Comput. 39 (2009), no. 3, 874–903. MR 2538842, DOI 10.1137/070705702
Phong Q. Nguyen and Jacques Stern, The two faces of lattices in cryptology, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 146–180. MR 1903893, DOI 10.1007/3-540-44670-2_{1}2
Phong Q. Nguyen and Brigitte Vallée (eds.), The LLL algorithm, Information Security and Cryptography, Springer-Verlag, Berlin, 2010. Survey and applications. MR 2722178, DOI 10.1007/978-3-642-02295-1
A. Novocin, D. Stehlé, and G. Villard, An LLL-reduction algorithm with quasi-linear time complexity, Accepted to STOC 2011.
C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), no. 1, 47–62. MR 925597, DOI 10.1016/0196-6774(88)90004-1
Claus Peter Schnorr, Fast LLL-type lattice reduction, Inform. and Comput. 204 (2006), no. 1, 1–25. MR 2192577, DOI 10.1016/j.ic.2005.04.004
—, Progress on LLL and lattice reduction, In [20], 2009.
A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Informatica 1 (1971), 139–144.
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
Gilles Villard, Certification of the $QR$ factor $R$ and of lattice basis reducedness, ISSAC 2007, ACM, New York, 2007, pp. 361–368. MR 2402283, DOI 10.1145/1277548.1277597
Hong Yuan Zha, A componentwise perturbation analysis of the $QR$ decomposition, SIAM J. Matrix Anal. Appl. 14 (1993), no. 4, 1124–1131. MR 1238926, DOI 10.1137/0614076