{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T16:31:03Z","timestamp":1792600263252,"version":"4.5.0"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>The Lenstra\u2013Lenstra\u2013Lov\u00e1sz lattice basis reduction algorithm (called LLL or ${\\rm L}^3$) is a fundamental tool in computational number theory and theoretical computer science, which can be viewed as an efficient algorithmic version of Hermite's inequality on Hermite's constant. Given an integer d-dimensional lattice basis with vectors of Euclidean norm less than B in an n-dimensional space, the ${\\rm L}^3$ algorithm outputs a reduced basis in $O(d^3n\\,{\\rm log}\\,B\\cdot\\mathcal{M}(d\\,{\\rm log}\\,B))$ bit operations, where $\\mathcal{M}(k)$ denotes the time required to multiply k-bit integers. This worst-case complexity is problematic for applications where d or\/and ${\\rm log}\\,B$ are often large. As a result, the original ${\\rm L}^3$ algorithm is almost never used in practice, except in tiny dimension. Instead, one applies floating-point variants where the long-integer arithmetic required by Gram\u2013Schmidt orthogonalization is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst case: the usual floating-point ${\\rm L}^3$ algorithm is not even guaranteed to terminate, and the output basis may not be ${\\rm L}^3$-reduced at all. In this article, we introduce the ${\\rm L}^2$ algorithm, a new and natural floating-point variant of the ${\\rm L}^3$ algorithm which provably outputs ${\\rm L}^3$-reduced bases in polynomial time $O(d^2n(d+{\\rm log}\\,B)\\,{\\rm log}\\,B\\cdot\\mathcal{M}(d))$. This is the first ${\\rm L}^3$ algorithm whose running time (without fast integer arithmetic) provably grows only quadratically with respect to ${\\rm log}\\,B$, like Euclid's gcd algorithm and Lagrange's two-dimensional algorithm.<\/jats:p>","DOI":"10.1137\/070705702","type":"journal-article","created":{"date-parts":[[2009,8,26]],"date-time":"2009-08-26T18:10:21Z","timestamp":1251310221000},"page":"874-903","source":"Crossref","is-referenced-by-count":121,"title":["An LLL Algorithm with Quadratic Complexity"],"prefix":"10.1137","volume":"39","author":[{"given":"Phong Q.","family":"Nguyen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Damien","family":"Stehl\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,8,26]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A. Akhavi,\n                      Worst-case complexity of the optimal LLL algorithm\n                      , in Proceedings of the 2000 Latin American Theoretical Informatics (LATIN 2000), Lecture Notes in Comput. Sci. 1776, Springer, Berlin, 2000, pp. 355\u2013366.","DOI":"10.1007\/10719839_35"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579403"},{"key":"R3","unstructured":"C. Batut, K. Belabas, D. Bernardi, H. Cohen, and M. Olivier,\n                      PARI\/GP Computer Package Version\n                      2, Universit\u00e9 de Bordeaux I, Talence, France."},{"key":"R4","first-page":"203","volume":"46","author":"Boneh D.","year":"1999","journal-title":"Notices Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9920","issn-type":"print"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"D. Boneh and G. Durfee,\n                      \n                        Cryptanalysis of RSA with private key\n                        d\n                        less than $n^{0.292}$\n                      \n                      , in Proceedings of Eurocrypt '99, Lecture Notes in Comput. Sci. 1592, Springer, Berlin, 1999, pp. 1\u201311.","DOI":"10.1007\/3-540-48910-X_1"},{"key":"R6","unstructured":"H. Cohen,\n                      A Course in Computational Algebraic Number Theory\n                      , Springer, Berlin, 1995."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900030"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"N. Gama, N. Howgrave-Graham, H. Koy, and P. Q. Nguyen,\n                      Rankin's constant and blockwise lattice reduction\n                      , in Advances in Cryptology, Proceedings of CRYPTO '06, Lecture Notes in Comput. Sci. 4117, Springer, Berlin, 2006, pp. 112\u2013130.","DOI":"10.1007\/11818175_7"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"N. Gama and P. Q. Nguyen,\n                      Finding short lattice vectors within Mordell's inequality\n                      , in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC '08), ACM, New York, 2008.","DOI":"10.1145\/1374376.1374408"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"C. Gauss,\n                      Disquisitiones Arithmeticae\n                      , G. Fleischer, Leipzig, 1801.","DOI":"10.5479\/sil.324926.39088000932822"},{"key":"R11","unstructured":"G. H. Golub and Charles F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer, Berlin, 1993.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1850.40.279"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0914050"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011214926272"},{"key":"R16","first-page":"9","volume":"22","author":"Ieee","year":"1987","journal-title":"; reprinted in ACM SIGPLAN Notices"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"E. Kaltofen,\n                      On the complexity of finding short vectors in integer lattices\n                      , in Proceedings of EUROCAL'83, Lecture Notes in Comput. Sci. 162, Springer, Berlin, 1983, pp. 236\u2013244.","DOI":"10.1007\/3-540-12868-9_107"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"H. Koy and C. P. Schnorr,\n                      Segment LLL-reduction of lattice bases\n                      , in Cryptography and Lattices, Proceedings of CALC'01, Lecture Notes in Comput. Sci. 2146, Springer, Berlin, 2001, pp. 67\u201380.","DOI":"10.1007\/3-540-44670-2_7"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"H. Koy and C. P. Schnorr,\n                      Segment LLL-reduction of lattice bases with floating-point orthogonalization\n                      , in Cryptography and Lattices, Proceedings of CALC'01, Lecture Notes in Comput. Sci. 2146, Springer, Berlin, 2001, pp. 81\u201396.","DOI":"10.1007\/3-540-44670-2_8"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2461"},{"key":"R21","unstructured":"L. Lagrange,\n                      Recherches d'arithm\u00e9tique\n                      , Nouv. M\u00e9m. Acad., Berlin, 1773."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"C. L. Lawson and R. J. Hanson,\n                      Solving Least Squares Problems\n                      , SIAM, Philadelphia, 1995.","DOI":"10.1137\/1.9781611971217"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"R24","unstructured":"H. W. Lenstra, Jr.\n                      Integer Programming with a Fixed Number of Variables\n                      , Technical report 81-03, Mathematisch Instituut, Universiteit van Amsterdam, Amsterdam, The Netherlands, 1981."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"H. W. Lenstra, Jr.\n                      Flags and lattice basis reduction\n                      , in Proceedings of the Third European Congress of Mathematics, Vol. 1, Birkh\u00e4user, Basel, 2001, pp. 37\u201351.","DOI":"10.1007\/978-3-0348-8268-2_3"},{"key":"R27","unstructured":"Lidia,\n                      A Library for Computational Number Theory\n                      , http:\/\/www-jb.cs.uni-sb.de\/LiDIA\/linkhtml\/lidia\/lidia.html."},{"key":"R28","unstructured":"Magma,\n                      The Magma Computational Algebra System for Algebra, Number Theory and Geometry\n                      , http:\/\/magma.maths.usyd.edu.au\/magma\/."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"D. Micciancio and S. Goldwasser,\n                      Complexity of Lattice Problems: A Cryptographic Perspective\n                      , Kluwer Internat. Ser. Engrg. Comput. Sci. 671, Kluwer Academic Publishers, Boston, MA, 2002.","DOI":"10.1007\/978-1-4615-0897-7_8"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"P. Nguyen,\n                      Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto\n                      '97, in Proceedings of the 19th IACR Cryptology Conference (Crypto '99), Lecture Notes in Comput. Sci. 1666, Springer, Berlin, 1999, pp. 288\u2013304.","DOI":"10.1007\/3-540-48405-1_18"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"P. Nguyen and J. Stern,\n                      Cryptanalysis of the Ajtai-Dwork cryptosystem\n                      , in Proceedings of the 18th IACR Cryptology Conference (Crypto '98), Lecture Notes in Comput. Sci. 1462, Springer, Berlin, 1998, pp. 223\u2013242.","DOI":"10.1007\/BFb0055731"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-002-0021-3"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen and D. Stehl\u00e9,\n                      Low-dimensional lattice basis reduction revisited (extended abstract)\n                      , in Proceedings of the 6th International Algorithmic Number Theory Symposium (ANTS-VI), Lecture Notes in Comput. Sci. 3076, Springer, Berlin, 2004, pp. 338\u2013357.","DOI":"10.1007\/978-3-540-24847-7_26"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen and D. Stehl\u00e9,\n                      Floating-point LLL revisited\n                      , in Advances in Cryptology\u2014Proceedings of EUROCRYPT '05, Lecture Notes in Comput. Sci. 3494, Springer, Berlin, 2005, pp. 215\u2013233.","DOI":"10.1007\/11426639_13"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen and D. Stehl\u00e9,\n                      LLL on the average\n                      , in Proceedings of the 7th International Algorithmic Number Theory Symposium (ANTS-VII), Lecture Notes in Comput. Sci. 4076, Springer, Berlin, 2006, pp. 238\u2013256.","DOI":"10.1007\/11792086_18"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen and J. Stern,\n                      The two faces of lattices in cryptology\n                      , in Proceedings of CALC '01, Lecture Notes in Comput. Sci. 2146, Springer, Berlin, 2001, pp. 146\u2013180.","DOI":"10.1007\/3-540-44670-2_12"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"A. M. Odlyzko,\n                      The rise and fall of knapsack cryptosystems\n                      , in Cryptology and Computational Number Theory, Proc. Sympos. Appl. Math. 42, AMS, Providence, RI, 1990, pp. 75\u201388.","DOI":"10.1090\/psapm\/042\/1095552"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(87)80061-5"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90004-1"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.04.004"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581144"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage,\n                      Factorization of univariate integer polynomials by Diophantine approximation and improved basis reduction algorithm\n                      , in Proceedings of the 1984 International Colloquium on Automata, Languages and Programming (ICALP 1984), Lecture Notes in Comput. Sci. 172, Springer, Berlin, 1984, pp. 436\u2013447.","DOI":"10.1007\/3-540-13345-3_40"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage,\n                      Fast reduction and composition of binary quadratic forms\n                      , in Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC'91), ACM, New York, 1991, pp. 128\u2013133.","DOI":"10.1145\/120694.120711"},{"key":"R45","unstructured":"V. Shoup,\n                      Number Theory C++ Library (NTL)\n                      , http:\/\/www.shoup.net\/ntl\/."},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-05-01729-1"},{"key":"R47","unstructured":"D. Stehl\u00e9,\n                      Floating-point LLL: Theoretical and practical aspects\n                      , in Proceedings of LLL + 25, P. Q. Nguyen and B. Vall\u00e9e, eds., Springer, Berlin, to appear."},{"key":"R48","unstructured":"A. Storjohann,\n                      Faster Algorithms for Integer Lattice Basis Reduction\n                      , Technical report, ETH Z\u00fcrich, Z\u00fcrich, Switzerland, 1996."},{"key":"R49","unstructured":"The SPACES Project,\n                      MPFR, a LGPL-Library for Multiple-Precision Floating-Point Computations with Exact Rounding\n                      , http:\/\/www.mpfr.org\/."},{"key":"R50","unstructured":"J. H. Wilkinson,\n                      The Algebraic Eigenvalue Problem\n                      , The Clarendon Press, Oxford University Press, New York, 1988."},{"key":"R51","doi-asserted-by":"crossref","unstructured":"C. K. Yap,\n                      Fast unimodular reduction: Planar integer lattices\n                      , in Proceedings of the 1992 Symposium on the Foundations of Computer Science (FOCS 1992), IEEE Computer Society, Los Alamitos, CA, 1992, pp. 437\u2013446.","DOI":"10.1109\/SFCS.1992.267808"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070705702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:32:50Z","timestamp":1787337170000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070705702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070705702"],"URL":"https:\/\/doi.org\/10.1137\/070705702","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}