{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T04:52:29Z","timestamp":1767675149680,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":55,"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_7","type":"book-chapter","created":{"date-parts":[[2009,11,18]],"date-time":"2009-11-18T18:20:09Z","timestamp":1258568409000},"page":"265-282","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Selected Applications of LLL in Number Theory"],"prefix":"10.1007","author":[{"given":"Denis","family":"Simon","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,10,7]]},"reference":[{"key":"7_CR1_7","doi-asserted-by":"crossref","first-page":"2201","DOI":"10.1109\/TIT.2002.800499","volume":"48","author":"E. Agrell","year":"2002","unstructured":"E. Agrell, T. Eriksson, A. Vardy, K. Zeger: Closest point search in lattices, IEEE Trans. Inf. Theory 48, No. 8, 2201\u20132214 (2002).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"7_CR2_7","doi-asserted-by":"crossref","unstructured":"G. Almkvist, A.J. Granville: Borwein and Bradley\u2019s Ap\u00e9ry-like formulae for \u03b6(4n + 3), Exp. Math. 8, No. 2, 197\u2013203 (1999).","DOI":"10.1080\/10586458.1999.10504398"},{"key":"7_CR3_7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"L. Babai: On Lov\u00e1sz lattice reduction and the nearest lattice point problem, Combinatorica 6, 1\u201313 (1986).","journal-title":"Combinatorica"},{"key":"7_CR4_7","doi-asserted-by":"crossref","unstructured":"K. Belabas: Topics in computational algebraic number theory, J. Th\u00e9or. Nombres Bordeaux 16, No. 1, 19\u201363 (2004).","DOI":"10.5802\/jtnb.433"},{"key":"7_CR5_7","doi-asserted-by":"crossref","unstructured":"J. Borwein, D. Bradley: Empirically determined Ap\u00e9ry-like formulae for \u03b6(4n + 3), Exp. Math. 6, No. 3, 181\u2013194 (1997).","DOI":"10.1080\/10586458.1997.10504608"},{"key":"7_CR6_7","doi-asserted-by":"crossref","unstructured":"J. Borwein, D. Bradley: Experimental determination of Ap\u00e9ry-like identities for \u03b6(2n + 2), Exp. Math. 15, No. 3, 281\u2013289 (2006).","DOI":"10.1080\/10586458.2006.10128968"},{"key":"#cr-split#-7_CR7_7.1","doi-asserted-by":"crossref","unstructured":"W. Bosma, P. Stevenhagen: On the computation of quadratic 2-class groups J. Th\u00e9or. Nombres Bordeaux. 8, No. 2, 283-313 (1996)","DOI":"10.5802\/jtnb.170"},{"key":"#cr-split#-7_CR7_7.2","doi-asserted-by":"crossref","unstructured":"erratum ibid. 9, No. 1, 249 (1997).","DOI":"10.5802\/jtnb.200"},{"key":"7_CR8_7","unstructured":"J. Buchmann: A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, S\u00e9min. Th\u00e9or. Nombres, Paris\/Fr. 1988\u201389, Prog. Math. 91, 27\u201341 (1990)."},{"key":"7_CR9_7","unstructured":"J. Buchmann, S. D\u00fcllmann: A probabilistic class group and regulator algorithm and its implementation, Computational number theory, Proc. Colloq., Debrecen\/Hung. 1989, 53\u201372 (1991)."},{"key":"7_CR10_7","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1017\/S0305004100034009","volume":"55","author":"JWS Cassels","year":"1959","unstructured":"J.W.S. Cassels: Note on quadratic forms over the rational field , Proc. Cambridge Philos. Soc. 55, 267\u2013270 (1959).","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"7_CR11_7","doi-asserted-by":"crossref","unstructured":"T. Cochrane, P. Mitchell: Small solutions of the Legendre equation, J. Number Theor. 70, No. 1, 62\u201366 (1998).","DOI":"10.1006\/jnth.1998.2221"},{"key":"7_CR12_7","unstructured":"H. Cohen: A Course in Computational Algebraic Number Theory, Graduate Texts in Math. 138, Second corrected printing, Springer, Berlin, (1995)."},{"key":"7_CR13_7","doi-asserted-by":"crossref","unstructured":"H. Cohen: Advanced Topics in Computational Algebraic Number Theory, Graduate Texts in Math. 193, Springer, Berlin, (2000).","DOI":"10.1007\/978-1-4419-8489-0"},{"key":"7_CR14_7","doi-asserted-by":"crossref","unstructured":"H. Cohen, F. Diaz y Diaz: A polynomial reduction algorithm, S\u00e9min. Th\u00e9or. Nombres Bordeaux., S\u00e9r. II 3, No. 2, 351\u2013360 (1991).","DOI":"10.5802\/jtnb.55"},{"key":"7_CR15_7","doi-asserted-by":"crossref","unstructured":"H. Cohen, F. Diaz y Diaz, M. Olivier: Subexponential algorithms for class group and unit computations, J. Symbolic Comput. 24, No. 3\u20134, 433\u2013441 (1997), Computational algebra and number theory (London, 1993).","DOI":"10.1006\/jsco.1996.0143"},{"key":"7_CR16_7","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1090\/S0025-5718-02-01480-1","volume":"72","author":"JE Cremona","year":"2003","unstructured":"J.E. Cremona, D. Rusin: Efficient solution of rational conics, Math. Comp. 72, 1417\u20131441 (2003).","journal-title":"Math. Comp."},{"key":"7_CR17_7","unstructured":"U. Dieter: Calculating shortest vectors in a lattice Ber. Math.-Stat. Sekt. Forschungszent. Graz 244, 14 p. (1985)."},{"key":"7_CR18_7","doi-asserted-by":"crossref","unstructured":"T. Dokchitser: LLL & ABC, J. Number Theor. 107, No. 1, 161\u2013167 (2004).","DOI":"10.1016\/j.jnt.2004.02.003"},{"key":"7_CR19_7","doi-asserted-by":"crossref","unstructured":"N.D. Elkies: Rational points near curves and small nonzero |x\n                        3\n                        \u2212 y\n                        2\n                        | via lattice reduction, W. Bosma (ed.), Algorithmic number theory. 4th international symposium. ANTS-IV, Leiden, the Netherlands, July 2\u20137, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1838, 33\u201363 (2000).","DOI":"10.1007\/10722028_2"},{"key":"7_CR20_7","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1090\/S0025-5718-99-00995-3","volume":"225","author":"H.R.P. Ferguson","year":"1999","unstructured":"H.R.P. Ferguson, D. Bailey, S. Arno: Analysis of PSLQ, an integer relation finding algorithm, Math. Comput. 68, No. 225, 351\u2013369 (1999).","journal-title":"Math. Comput."},{"key":"7_CR21_7","doi-asserted-by":"crossref","unstructured":"H.R.P. Ferguson, R.W. Forcade: Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two, Bull. Am. Math. Soc., New Ser. 1, 912\u2013914 (1979).","DOI":"10.1090\/S0273-0979-1979-14691-3"},{"key":"7_CR22_7","doi-asserted-by":"crossref","unstructured":"U. Fincke, M. Pohst: On reduction algorithms in non-linear integer mathematical programming, Operations research, Proc. 12th Annu. Meet., Mannheim 1983, 289\u2013295 (1984).","DOI":"10.1007\/978-3-642-69546-9_63"},{"key":"7_CR23_7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.2307\/2007966","volume":"44","author":"U Fincke","year":"1985","unstructured":"U. Fincke, M. Pohst: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comput. 44, 463\u2013471 (1985).","journal-title":"Math. Comput."},{"key":"7_CR24_7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-7560-0","volume-title":"Disquisitiones Arithmeticae","author":"CF Gauss","year":"1986","unstructured":"C.F. Gauss: Disquisitiones Arithmeticae, Springer, Berlin, (1986)."},{"key":"7_CR25_7","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1090\/S0894-0347-1989-1002631-0","volume":"4","author":"J. Hafner","year":"1989","unstructured":"J. Hafner, K. McCurley: A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2, No. 4, 837\u2013850 (1989).","journal-title":"J. Amer. Math. Soc."},{"key":"7_CR26_7","unstructured":"G. Hanrot: LLL: A tool for effective diophantine approximation, this volume."},{"key":"7_CR27_7","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1137\/0218059","volume":"18","author":"J. H\u00e5stad","year":"1989","unstructured":"J. H\u00e5stad, B. Just, J.C. Lagarias, C.P. Schnorr (B. Helfrich): Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18, No. 5, 859\u2013881 (1989).","journal-title":"SIAM J. Comput."},{"key":"#cr-split#-7_CR28_7.1","doi-asserted-by":"crossref","unstructured":"G. Havas, B.S. Majewski, K.R. Matthews: Extended GCD and Hermite normal form algorithms via lattice basis reduction, Exp. Math. 7, No. 2, 125-136 (1998)","DOI":"10.1080\/10586458.1998.10504362"},{"key":"#cr-split#-7_CR28_7.2","doi-asserted-by":"crossref","unstructured":"Addenda and errata: Extended GCD and Hermite normal form algorithms via lattice basis reduction, Exp. Math. 8, No. 2, 205 (1999).","DOI":"10.1080\/10586458.1999.10504399"},{"key":"7_CR29_7","doi-asserted-by":"crossref","unstructured":"G. Ivanyos, A. Sz\u00e1nto: Lattice basis reduction for indefinite forms and an application, Discrete Math. 153, No. 1\u20133, 177\u2013188 (1996).","DOI":"10.1016\/0012-365X(95)00135-J"},{"key":"7_CR30_7","first-page":"377","volume":"4","author":"G J\u00e4ger","year":"2005","unstructured":"G. J\u00e4ger. Reduction of Smith normal form transformation matrices Computing 74, No. 4,377\u2013388 (2005).","journal-title":"No."},{"key":"7_CR31_7","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, N. Yui: Explicit construction of the Hilbert class fields of imaginary quadratic fields by integer lattice reduction, Number theory, Proc. Semin., New York\/NY (USA)1989\u20131990, 149\u2013202 (1991).","DOI":"10.1007\/978-1-4757-4158-2_8"},{"key":"7_CR32_7","unstructured":"R. Kannan: Lattices, basis reduction and the shortest vector problem, Theory of algorithms, Colloq. P\u00e9cs\/Hung. 1984, Colloq. Math. Soc. J\u00e1nos Bolyai 44, 283\u2013311 (1986)."},{"key":"7_CR33_7","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1090\/S0025-5718-1988-0917831-4","volume":"50","author":"R. Kannan","year":"1988","unstructured":"R. Kannan, A.K. Lenstra, L. Lov\u00e1sz: Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. Comput. 50, No. 181, 235\u2013250 (1988).","journal-title":"Math. Comput."},{"key":"7_CR34_7","doi-asserted-by":"crossref","unstructured":"R. Kannan, L.A. McGeoch: Basis reduction and evidence for transcendence of certain numbers, Foundations of software technology and theoretical computer science, Proc. 6th Conf., New Delhi\/India 1986, Lect. Notes Comput. Sci. 241, 263\u2013269 (1986).","DOI":"10.1007\/3-540-17179-7_16"},{"key":"7_CR35_7","unstructured":"J. Kl\u00fcners: The van Hoeij algorithm for factoring polynomials, this volume."},{"key":"7_CR36_7","doi-asserted-by":"crossref","unstructured":"T. Kotnik, H. te Riele: The Mertens Conjecture Revisited, F. Hes, S. Pauli, M. Pohst (ed.), ANTS 2006 Berlin, Lect. Notes Comput. Sci. 4076, 156\u2013167 (2006).","DOI":"10.1007\/11792086_12"},{"key":"7_CR37_7","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0196-6774(80)90021-8","volume":"1","author":"JC Lagarias","year":"1980","unstructured":"J.C. Lagarias: Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithm. 1, 142\u2013186 (1980).","journal-title":"J. Algorithm."},{"key":"7_CR38_7","doi-asserted-by":"crossref","unstructured":"J.C. Lagarias: Knapsack public key cryptosystems and Diophantine approximation, in Advances in cryptology (Santa Barbara, Calif., 1983), 3\u201323, Plenum, New York, (1984).","DOI":"10.1007\/978-1-4684-4730-9_1"},{"key":"7_CR39_7","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0214016","volume":"14","author":"JC Lagarias","year":"1985","unstructured":"J.C. Lagarias: The computational complexity of simultaneous diophantine approximation problems, SIAM J. Comput. 14, 196\u2013209 (1985).","journal-title":"SIAM J. Comput."},{"key":"7_CR40_7","doi-asserted-by":"crossref","unstructured":"A.K. Lenstra: Polynomial factorization by root approximation, EUROSAM 84, Symbolic and algebraic computation, Proc. int. Symp., Cambridge\/Engl. 1984, Lect. Notes Comput. Sci. 174, 272\u2013276 (1984).","DOI":"10.1007\/BFb0032849"},{"key":"7_CR41_7","first-page":"515","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"A.K. Lenstra, H.W. Lenstra, L. Lov\u00e1sz: Factoring polynomials with rational coefficients Math. Ann. 261, 515\u2013534 (1982).","journal-title":"Ann."},{"key":"7_CR42_7","unstructured":"K. Matthews: www.numbertheory.org\/lll.html"},{"key":"7_CR43_7","doi-asserted-by":"crossref","unstructured":"A.M. Odlyzko, H. te Riele: Disproof of the Mertens conjecture J. Reine Angew. Math. 357, 138\u2013160 (1985).","DOI":"10.1515\/crll.1985.357.138"},{"key":"7_CR44_7","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0747-7171(87)80061-5","volume":"4","author":"M Pohst","year":"1987","unstructured":"M. Pohst: A modification of the LLL reduction algorithm, J. Symb. Comput. 4, 123\u2013127 (1987).","journal-title":"J. Symb. Comput."},{"key":"7_CR45_7","doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage: Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm, in Automata, languages and programming, 11th Colloq., Antwerp\/Belg. 1984, Lect. Notes Comput. Sci. 172, 436\u2013447 (1984).","DOI":"10.1007\/3-540-13345-3_40"},{"key":"7_CR46_7","unstructured":"J.-P. Serre: Cours d\u2019arithm\u00e9tique, P.U.F. 3rd edition (1988)."},{"key":"7_CR47_7","doi-asserted-by":"crossref","unstructured":"A. Shamir: A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem, in 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982), 145\u2013152, IEEE, New York, (1982)","DOI":"10.1109\/SFCS.1982.5"},{"key":"#cr-split#-7_CR48_7.1","doi-asserted-by":"crossref","unstructured":"D. Shanks: Gauss's ternary form reduction and the 2-Sylow subgroup, Math. Comput. 25,837-853 (1971)","DOI":"10.1090\/S0025-5718-1971-0297737-4"},{"key":"#cr-split#-7_CR48_7.2","doi-asserted-by":"crossref","unstructured":"Corrigendum: Gauss's ternary form reduction and the 2-Sylow subgroup, Math. Comput. 32, 1328-1329 (1978).","DOI":"10.1090\/S0025-5718-1978-0491495-2"},{"key":"7_CR49_7","doi-asserted-by":"crossref","unstructured":"D. Simon: Solving quadratic equations using reduced unimodular quadratic forms, Math. Comput. 74, No. 251, 1531\u20131543 (2005).","DOI":"10.1090\/S0025-5718-05-01729-1"},{"key":"7_CR50_7","unstructured":"D. Simon: Quadratic equations in dimensions 4, 5, and more, preprint (2006)."},{"key":"7_CR51_7","unstructured":"N.P. Smart: The algorithmic resolution of diophantine equations, London Mathematical Society Student Texts. 41. Cambridge: Cambridge University Press. (1998)."},{"issue":"1","key":"7_CR52_7","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/0022-314X(86)90059-4","volume":"24","author":"BMM de Weger","year":"1986","unstructured":"B.M.M. de Weger: Approcimation lattices of p-adic numbers, J. Number Theor., 24(1), 70\u201388 (1986).","journal-title":"J. Number Theor."}],"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_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T21:57:19Z","timestamp":1674856639000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02295-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022944","9783642022951"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02295-1_7","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"}}]}}