{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:37:09Z","timestamp":1765960629904,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642022944"},{"type":"electronic","value":"9783642022951"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02295-1_3","type":"book-chapter","created":{"date-parts":[[2009,11,18]],"date-time":"2009-11-18T18:20:09Z","timestamp":1258568409000},"page":"71-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Probabilistic Analyses of Lattice Reduction Algorithms"],"prefix":"10.1007","author":[{"given":"Brigitte","family":"Vall\u00e9e","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Vera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,10,7]]},"reference":[{"key":"3_CR1_3","unstructured":"K. Aardal and F. Eisenbrand. The LLL algorithm and integer programming, This book"},{"key":"3_CR2_3","unstructured":"M. Ajtai. Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr\u2019s algorithm for the shortest vector problem. Theory of Computing 4(1): 21\u201351 (2008)"},{"key":"3_CR3_3","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S0304-3975(01)00251-1","volume":"287","author":"A. Akhavi","year":"2002","unstructured":"A. Akhavi. Random lattices, threshold phenomena and efficient reduction algorithms, Theoretical Computer Science, 287, (2002), 359\u2013385","journal-title":"Theoretical Computer Science"},{"key":"3_CR4_3","unstructured":"A. Akhavi, J.-F. Marckert , and A. Rouault. On the reduction of a random basis, Proceedings of SIAM-ALENEX\/ANALCO\u201907. New-Orleans, January 07, long version to appear in ESAIM Probability and Statistics"},{"key":"3_CR5_3","doi-asserted-by":"crossref","unstructured":"A. Akhavi and B. Vall\u00e9e. Average bit-complexity of Euclidean algorithms, In Proceedings of ICALP\u20192000 \u2013 Gen\u00e8ve, 14 pages, LNCS, 373\u2013387, (1853)","DOI":"10.1007\/3-540-45022-X_32"},{"key":"3_CR6_3","doi-asserted-by":"crossref","unstructured":"V. Baladi and B. Vall\u00e9e. Euclidean algorithms are Gaussian, Journal of Number Theory, 110(2), (2005), 331\u2013386","DOI":"10.1016\/j.jnt.2004.08.008"},{"key":"3_CR7_3","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/S0196-6774(02)00218-3","volume":"44","author":"J. Bourdon","year":"2002","unstructured":"J. Bourdon, B. Daireaux, and B. Vall\u00e9e. Dynamical analysis of \u03b1-Euclidean algorithms, Journal of Algorithms, 44, (2002), 246\u2013285","journal-title":"Journal of Algorithms"},{"key":"3_CR8_3","doi-asserted-by":"crossref","unstructured":"D. Bump. Automorphic Forms and Representations, Cambridge University Press, Cambridge, (1996)","DOI":"10.1017\/CBO9780511609572"},{"key":"3_CR9_3","doi-asserted-by":"crossref","unstructured":"F. Chazal, V. Maume-Deschamps, and B. Vall\u00e9e. Erratum to \u201cDynamical sources in information theory: fundamental intervals and word prefixes\u201d, Algorithmica, 38, (2004), 591\u2013596","DOI":"10.1007\/s00453-003-1057-y"},{"key":"3_CR10_3","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1016\/j.jsc.2008.04.018","volume":"44","author":"E. Cesaratto","year":"2009","unstructured":"E. Cesaratto, J. Cl\u00e9ment, B. Daireaux, L. Lhote, V. Maume-Deschamps and B. Vall\u00e9e. Analysis of fast versions of the Euclid algorithm, Journal of Symbolic Computation, 44 (2009) pp 726-767","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"3_CR11_3","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D. Coppersmith","year":"1997","unstructured":"D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10(4), (1997), 233\u2013260","journal-title":"Journal of Cryptology"},{"key":"3_CR12_3","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and A. Shamir. Lattice attacks on NTRU, Proceedings of Eurocrypt 1997, LNCS, 1233, 52\u201361, Springer, Berlin, (1997)","DOI":"10.1007\/3-540-69053-0_5"},{"key":"3_CR13_3","doi-asserted-by":"crossref","unstructured":"J.-S. Coron. Security proof for partial-domain hash signature schemes. In Proceedings of Crypto 2002, LNCS, 2442, 613\u2013626, Springer, Berlin, (2002)","DOI":"10.1007\/3-540-45708-9_39"},{"key":"3_CR14_3","doi-asserted-by":"crossref","unstructured":"H. Daud\u00e9, P. Flajolet, and B. Vall\u00e9e. An average-case analysis of the Gaussian algorithm for lattice reduction, Combinatorics, Probability and Computing 6, (1997), 397\u2013433","DOI":"10.1017\/S0963548397003258"},{"issue":"1","key":"3_CR15_3","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(94)90071-X","volume":"123","author":"H. Daud\u00e9","year":"1994","unstructured":"H. Daud\u00e9 and B. Vall\u00e9e. An upper bound on the average number of iterations of the LLL algorithm. Theoretical Computer Science 123(1), (1994), 95\u2013115","journal-title":"Theoretical Computer Science"},{"key":"3_CR16_3","unstructured":"P. Flajolet and B. Vall\u00e9e. Gauss\u2019 reduction algorithm : an average case analysis, Proceedings of IEEE-FOCS 90, St-Louis, Missouri, 2, 830\u201339"},{"key":"3_CR17_3","unstructured":"P. Flajolet and B. Vall\u00e9e. Continued fractions, comparison algorithms and fine structure constants Constructive, Experimental and Non-Linear Analysis, Michel Thera, Editor, Proceedings of Canadian Mathematical Society, 27, 53\u201382, (2000)"},{"key":"3_CR18_3","unstructured":"C. Gentry. The geometry of provable security: some proofs of security in which lattices make a surprise appearance, This book"},{"key":"3_CR19_3","doi-asserted-by":"crossref","unstructured":"C. Gentry. How to compress rabin ciphertexts and signatures (and more), Proceedings of Crypto\u201904, 179\u2013200, Springer, Berlin, (2004)","DOI":"10.1007\/978-3-540-28628-8_11"},{"key":"3_CR20_3","doi-asserted-by":"crossref","unstructured":"D. Goldstein and A. Mayer. On the equidistribution of Hecke points, Forum Mathematicum, 15, (2003), 165\u2013189","DOI":"10.1515\/form.2003.009"},{"key":"3_CR21_3","unstructured":"G. Hanrot. LLL: a tool for effective diophantine approximation, This book"},{"key":"3_CR22_3","unstructured":"J. Kl\u00fcners. The van Hoeij algorithm for factoring polynomials, This book"},{"issue":"2","key":"3_CR23_3","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/0196-6774(80)90021-8","volume":"1","author":"J. C. Lagarias","year":"1980","unstructured":"J. C. Lagarias. Worst-case complexity bounds for algorithms in the theory of integral quadratic forms. Journal of Algorithms 1(2), (1980), 142\u2013186","journal-title":"Journal of Algorithms"},{"key":"3_CR24_3","doi-asserted-by":"crossref","unstructured":"H. Laville and B. Vall\u00e9e. Distribution de la constante d\u2019Hermite et du plus court vecteur dans les r\u00e9seaux de dimension 2, Journal de Th\u00e9orie des nombres de Bordeaux 6, (1994), 135\u2013159","DOI":"10.5802\/jtnb.110"},{"key":"3_CR25_3","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra, H. W. Lenstra, and L. Lov\u00e1sz. Factoring polynomials with rational coefficients. Mathematische Annalen 261, (1982), 513\u2013534","DOI":"10.1007\/BF01457454"},{"key":"3_CR26_3","unstructured":"L. Lhote. Computation of a class of continued fraction constants. Proceedings of ALENEX-ANALCO\u201904, 199\u2013210"},{"key":"3_CR27_3","doi-asserted-by":"crossref","unstructured":"L. Lhote and B. Vall\u00e9e. Gaussian laws for the main parameters of the Euclid algorithm, Algorithmica (2008), 497\u2013554","DOI":"10.1007\/s00453-007-9009-6"},{"key":"3_CR28_3","unstructured":"A. May. Using LLL reduction for solving RSA and factorization problems, This book"},{"key":"3_CR29_3","doi-asserted-by":"crossref","unstructured":"P. Nguyen and D. Stehl\u00e9. Floating-point LLL revisited, Proceedings of Eurocrypt 2005 , LNCS, 3494, 215\u2013233, Springer, Berlin, (2005)","DOI":"10.1007\/11426639_13"},{"key":"3_CR30_3","doi-asserted-by":"crossref","unstructured":"P. Nguyen and D. Stehl\u00e9. LLL on the average, Proceedings of the 7th Algorithmic Number Theory Symposium (ANTS VII), LNCS, 4076, 238\u2013256, Springer, Berlin, (2006)","DOI":"10.1007\/11792086_18"},{"key":"3_CR31_3","unstructured":"J. Hoffstein, N. Howgrave-Graham, J. Pipher, and W. Whyte. NTRUEncrypt and NTRUSign, This book."},{"key":"3_CR32_3","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms, Theoretical Computer Science, 53, (1987), 201\u2013224","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"3_CR33_3","doi-asserted-by":"crossref","unstructured":"I. Semaev. A 3-dimensional lattice reduction algorithm, Proceedings of the 2001 Cryptography and Lattices Conference (CALC\u201901), LNCS, 2146, 181\u2013193, Springer, Berlin, (2001)","DOI":"10.1007\/3-540-44670-2_13"},{"key":"3_CR34_3","doi-asserted-by":"crossref","unstructured":"C. L. Siegel. A mean value theorem in geometry of numbers, Annals in Mathematics, 46(2), (1945), 340\u2013347","DOI":"10.2307\/1969027"},{"key":"3_CR35_3","unstructured":"D. Simon. Selected applications of LLL in number theory, This book"},{"key":"3_CR36_3","unstructured":"D. Stehl\u00e9. Floating point LLL: theoretical and practical aspects, This book."},{"key":"3_CR37_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e. Euclidean Dynamics, Discrete and Continuous Dynamical Systems, 15(1), (2006), 281\u2013352","DOI":"10.3934\/dcds.2006.15.281"},{"key":"3_CR38_3","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1016\/0196-6774(91)90033-U","volume":"12","author":"B. Vall\u00e9e","year":"1991","unstructured":"B. Vall\u00e9e. Gauss\u2019 algorithm revisited. Journal of Algorithms 12, (1991), 556\u2013572","journal-title":"Journal of Algorithms"},{"key":"3_CR39_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e. Algorithms for computing signs of 2 \u00d72 determinants: dynamics and average-case analysis, Proceedings of ESA\u201997 (5th Annual European Symposium on Algorithms) (Graz, September 97), LNCS, 1284, 486\u2013499","DOI":"10.1007\/3-540-63397-9_37"},{"key":"3_CR40_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e. Op\u00e9rateurs de Ruelle-Mayer g\u00e9n\u00e9ralis\u00e9s et analyse en moyenne des algorithmes de Gauss et d\u2019Euclide, Acta Arithmetica 81.2, (1997), 101\u2013144","DOI":"10.4064\/aa-81-2-101-144"},{"key":"3_CR41_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e. Dynamical analysis of a class of Euclidean algorithms, Theoretical Computer Science 297(1\u20133), (2003), 447\u2013486","DOI":"10.1016\/S0304-3975(02)00652-7"},{"key":"3_CR42_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e. An affine point of view on minima finding in integer lattices of lower dimensions. Proceedings of EUROCAL\u201987, LNCS, 378, 376\u2013378, Springer, Berlin, (1987)","DOI":"10.1007\/3-540-51517-8_141"},{"key":"3_CR43_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e. Generation of elements with small modular squares and provably fast integer factoring algorithms, Mathematics of Computation, 56(194), (1991), 823\u2013849","DOI":"10.1090\/S0025-5718-1991-1068808-2"},{"key":"3_CR44_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e. Provably fast integer factoring algorithm with quasi-uniform quadratic residues, Proceedings of ACM-STOC-89, Seattle, 98\u2013106","DOI":"10.1145\/73007.73016"},{"key":"3_CR45_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e and A. Vera. Lattice reduction in two-dimensions: analyses under realistic probabilistic models, Proceedings of the AofA\u201907 conference, Discrete Mathematics and Theoretical Computer Science, Proc. AH, (2007), 181\u2013216","DOI":"10.46298\/dmtcs.3549"},{"key":"3_CR46_3","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e, M. Girault, and P. Toffin. How to guess \u2113-th roots modulo n by reducing lattices bases, Proceedings of AAECC-88, Rome, LNCS, (357), 427\u2013442","DOI":"10.1007\/3-540-51083-4_78"},{"key":"3_CR47_3","unstructured":"A. Vera. Analyses de l\u2019algorithme de Gauss. Applications \u00e0 l\u2019analyse de l\u2019algorithme LLL, PhD Thesis, University of Caen, (July 2009)"},{"key":"3_CR48_3","doi-asserted-by":"crossref","unstructured":"G. Villard. Parallel lattice basis reduction. Proceedings of International Symposium on Symbolic and Algebraic Computation, Berkeley, ACM, (1992)","DOI":"10.1145\/143242.143327"}],"container-title":["Information Security and Cryptography","The LLL Algorithm"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02295-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T08:59:10Z","timestamp":1739437150000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02295-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022944","9783642022951"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02295-1_3","relation":{},"ISSN":["1619-7100"],"issn-type":[{"type":"print","value":"1619-7100"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"7 October 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}