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
Additional Information
- Xiao-Wen Chang
- Affiliation: School of Computer Science, McGill University Montreal, Quebec, Canada H3A 2A7
- Email: chang@cs.mcgill.ca
- Damien Stehlé
- Affiliation: CNRS, Université de Lyon, Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, 46 Allée d’Italie, 69364 Lyon Cedex 07, France
- Email: damien.stehle@ens-lyon.fr
- Gilles Villard
- Affiliation: CNRS, Université de Lyon, Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, 46 Allée d’Italie, 69364 Lyon Cedex 07, France
- Email: gilles.villard@ens-lyon.fr
- Received by editor(s): September 4, 2009
- Received by editor(s) in revised form: March 17, 2011
- Published electronically: February 17, 2012
- Additional Notes: Xiao-Wen Chang’s work was supported by NSERC of Canada Grant RGPIN217191-07
Damien Stehlé’s work was partly funded by the LaRedA ANR project
Gilles Villard’s work was partly funded by the Gecko ANR project - © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 81 (2012), 1487-1511
- MSC (2010): Primary 11H06, 65F25; Secondary 11Y99, 65F35
- DOI: https://doi.org/10.1090/S0025-5718-2012-02545-2
- MathSciNet review: 2904587