Article Contents
Article Contents

# Certified lattice reduction

This work has been supported in part by the European Union as H2020 Programme under grant agreement number ERC-669891

• Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra–Lenstra–Lovász reduction algorithm (so-called LLL) has been improved in many ways through the past decades and remains one of the central methods used for reducingintegrallattice basis. In particular, its floating-point variants---where the rational arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic---are now the fastest known. However, the systematic study of the reduction theory ofrealquadratic forms or, more generally, of real lattices is not widely represented in the literature. When the problem arises, the lattice is usually replaced by an integral approximation of (a multiple of) the original lattice, which is then reduced. While practically useful and proven in some special cases, this method doesn't offer any guarantee of success in general. In this work, we present an adaptive-precision version of a generalized LLL algorithm that covers this case in all generality. In particular, we replace floating-point arithmetic by Interval Arithmetic to certify the behavior of the algorithm. We conclude by giving a typical application of the result in algebraic number theory for the reduction of ideal lattices in number fields.

Mathematics Subject Classification: 11H06, 11H55, 11R04.

 Citation:

• Figure 1.  Basic arithmetic operators in Interval Arithmetic

•  [1] K. Belabas, Topics in computational algebraic number theory, J. Théor. Nombres Bordeaux, 16 (2004), 19-63.  doi: 10.5802/jtnb.433. [2] J.-F. Biasse and C. Fieker, Improved techniques for computing the ideal class group and a system of fundamental units in number fields, The Open Book Series, 1 (2013), 113-133.  doi: 10.2140/obs.2013.1.113. [3] J. Buchmann, Reducing lattice bases by means of approximations, Algorithmic Number Theory (Ithaca, NY, 1994), Lecture Notes in Comput. Sci., Springer, Berlin, 877 (1994), 160–168. doi: 10.1007/3-540-58691-1_54. [4] H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag New York, Inc., New York, NY, USA, 1993. doi: 10.1007/978-3-662-02945-9. [5] B. M. M. de Weger, Solving exponential Diophantine equations using lattice basis reduction algorithms, J. Number theory, 26 (1987), 325-367.  doi: 10.1016/0022-314X(87)90088-6. [6] N. D. Elkies, Rational points near curves and small nonzero $|x^3-y^2|$ via lattice reduction, Algorithmic Number Theory: 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000, Proceedings, 1838 (2000), 33–63. doi: 10.1007/10722028_2. [7] A. Gélin and A. Joux, Reducing number field defining polynomials: An application to class group computations, LMS J. Comput. Math., 19 (2016), 315-331.  doi: 10.1112/S1461157016000255. [8] X. Gourdon, Combinatoire, algorithmique et géométrie des polynomes, PhD thesis, 27–49. [9] G. Havas, B. S. Majewski and K. R. Matthews, Extended GCD and Hermite normal form algorithms via lattice basis reduction, Experimental Mathematics, 7 (1998), 125-136.  doi: 10.1080/10586458.1998.10504362. [10] G. Jäger, Reduction of Smith normal form transformation matrices, Computing, 74 (2005), 377-388.  doi: 10.1007/s00607-004-0104-0. [11] L. Jaulin, M. Kieffer, O. Didrit and É. Walter, Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics, Springer Verlag, 2001. doi: 10.1007/978-1-4471-0249-6. [12] E. Kaltofen, On the complexity of finding short vectors in integer lattices, in Computer Algebra, EUROCAL '83, European Computer Algebra Conference (ed. J. A. van Hulzen), Lecture Notes in Computer Science, Springer, 162 (1983), 236–244. doi: 10.1007/3-540-12868-9_107. [13] S. Kim and A. Venkatesh, The behavior of random reduced bases, International Mathematics Research Notices, 2018 (2018), 6442-6480.  doi: 10.1093/imrn/rnx074. [14] A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.  doi: 10.1007/BF01457454. [15] H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res., 8 (1983), 538-548.  doi: 10.1287/moor.8.4.538. [16] H. W. Lenstra Jr. and A. Silverberg, Lattices with symmetry, Journal of Cryptology, 30 (2017), 760-804.  doi: 10.1007/s00145-016-9235-7. [17] L. Lovász and H. E. Scarf, The generalized basis reduction algorithm, Math. Oper. Res., 17 (1992), 751-764.  doi: 10.1287/moor.17.3.751. [18] R. E. Moore, Interval Arithmetic and Automatic Error Analysis in Digital Computing, PhD Thesis, Stanford, 1962. [19] R. E. Moore, Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, 2. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1979. [20] P. Q. Nguyen, Hermite's Constant and Lattice Algorithms, in The LLL algorithm (eds. P. Q. Nguyen and B. Vallée), Springer, 2010. [21] P. Q. Nguyen and D. Stehlé, An LLL algorithm with quadratic complexity, SIAM J. of Computing, 39 (2009), 874-903.  doi: 10.1137/070705702. [22] G. Pataki and M. Tural, On Sublattice Determinants in Reduced Bases, 2008. [23] M. Pohst, A modification of the LLL reduction algorithm, Journal of Symbolic Computation, 4 (1987), 123-127.  doi: 10.1016/S0747-7171(87)80061-5. [24] H. Ratschek and  J. Rokne,  New Computer Methods for Global Optimization, Halsted Press, New York, NY, USA, 1988. [25] C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci., 53 (1987), 201-224.  doi: 10.1016/0304-3975(87)90064-8. [26] C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms, 9 (1988), 47-62.  doi: 10.1016/0196-6774(88)90004-1. [27] C.-P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program., 66 (1994), 181-199.  doi: 10.1007/BF01581144. [28] T. Sunaga, Theory of an interval algebra and its application to numerical analysis, Japan J. Indust. Appl. Math., 26 (2009), 125-143.  doi: 10.1007/BF03186528. [29] FPLLL development team, Fplll, a lattice reduction library, 2016, Available at URL https://github.com/fplll/fplll. [30] G. Villard, Certification of the $QR$ factor $R$ and of lattice basis reducedness, ISSAC 2007, ACM, New York, (2007), 361–368, . doi: 10.1145/1277548.1277597. [31] R. C. Young, The algebra of many-values quantities, Math. Ann., 104 (1931), 260-290.  doi: 10.1007/BF01457934.

Figures(1)