{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:36:07Z","timestamp":1765960567547},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540546207"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-46416-6_4","type":"book-chapter","created":{"date-parts":[[2007,8,6]],"date-time":"2007-08-06T18:02:07Z","timestamp":1186423327000},"page":"54-67","source":"Crossref","is-referenced-by-count":40,"title":["An Improved Low-Density Subset Sum Algorithm"],"prefix":"10.1007","author":[{"given":"M. J.","family":"Coster","sequence":"first","affiliation":[]},{"given":"B. A.","family":"LaMacchia","sequence":"additional","affiliation":[]},{"given":"A. M.","family":"Odlyzko","sequence":"additional","affiliation":[]},{"given":"C. P.","family":"Schnorr","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-1-4684-4730-9_2","volume-title":"Advances in Cryptology, Proceedings of Crypto\u2019 83","author":"E. F. Brickell","year":"1984","unstructured":"E. F. Brickell, Solving low density knapsacks. Advances in Cryptology, Proceedings of Crypto\u2019 83, Plenum Press, New York (1984), 25\u201337."},{"key":"4_CR2","unstructured":"E. F. Brickell, The cryptanalysis of knapsack cryptosystems. Applications of Discrete Mathematics, R. D. Ringeisen and F. S. Roberts, eds., SIAM (1988), 3\u201323."},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1109\/5.4443","volume":"76","author":"E. F. Brickell","year":"1988","unstructured":"E. F. Brickell and A. M. Odlyzko, Cryptanalysis: a survey of recent results, Proc. IEEE 76 (1988), 578\u2013593.","journal-title":"Proc. IEEE"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1109\/18.21214","volume":"IT-34","author":"B. Chor","year":"1988","unstructured":"B. Chor and R. Rivest, A knapsack-type public key cryptosystem based on arithmetic in finite fields, IEEE Trans. Information Theory IT-34 (1988), 901\u2013909.","journal-title":"IEEE Trans. Information Theory"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Y. Desmedt, What happened with knapsack cryptographic schemes?, Performance Limits in Communication, Theory and Practice, J. K. Skwirzynski, ed., Kluwer (1988), 113\u2013134.","DOI":"10.1007\/978-94-009-2794-0_7"},{"key":"4_CR6","unstructured":"P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Rept. 81-04, Dept. of Mathematics, Univ. of Amsterdam, 1981."},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1137\/0215038","volume":"15","author":"A. M. Frieze","year":"1986","unstructured":"A. M. Frieze, On the Lagarias-Odlyzko algorithm for the subset sum problem, SIAM J. Comput. 15(2) (May 1986), 536\u2013539.","journal-title":"SIAM J. Comput."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0218037","volume":"18","author":"M. L. Furst","year":"1989","unstructured":"M. L. Furst and R. Kannan, Succinct certificates for almost all subset sum problems, SIAM J. Comput. 18 (1989), 550\u2013558.","journal-title":"SIAM J. Comput."},{"key":"4_CR9","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company (1979)."},{"issue":"5","key":"4_CR10","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/0218059","volume":"18","author":"J. Hastad","year":"1989","unstructured":"J. Hastad, B. Just, J. C. Lagarias, and C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18(5) (October 1989), 859\u2013881.","journal-title":"SIAM J. Comput."},{"key":"4_CR11","unstructured":"A. Joux and J. Stern, Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems, Proceedings of Fundamentals of Computation Theory\u2019 91, to be published."},{"issue":"1","key":"4_CR12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"J. C. Lagarias","year":"1985","unstructured":"J. C. Lagarias and A. M. Odlyzko, Solving low-density subset sum problems, J. Assoc. Comp. Mach. 32(1) (January 1985), 229\u2013246.","journal-title":"J. Assoc. Comp. Mach."},{"key":"4_CR13","volume-title":"Basis Reduction Algorithms and Subset Sum Problems","author":"B. A. LaMacchia","year":"1991","unstructured":"B. A. LaMacchia, Basis Reduction Algorithms and Subset Sum Problems, SM Thesis, Dept. of Elect. Eng. and Comp. Sci., Massachusetts Institute of Technology, Cambridge, MA (1991)."},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra, and L. Lov\u00e1sz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515\u2013534.","journal-title":"Math. Ann."},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01571276","volume":"110","author":"J. E. Mazo","year":"1990","unstructured":"J. E. Mazo and A. M. Odlyzko, Lattice points in high-dimensional spheres, Monatsh. Math. 110 (1990), 47\u201361.","journal-title":"Monatsh. Math."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"A. M. Odlyzko, The rise and fall of knapsack cryptosystems, Cryptology and Computational Number Theory, C. Pomerance, ed., Am. Math. Soc., Proc. Symp. Appl. Math. 42 (1990), 75\u201388.","DOI":"10.1090\/psapm\/042\/1095552"},{"key":"4_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/3-540-18088-5_33","volume-title":"Automata, Languages, and Programming: 14thICALP","author":"A. Paz","year":"1987","unstructured":"A. Paz and C. P. Schnorr, Approximating integer lattices by lattices with cyclic factor groups, Automata, Languages, and Programming: 14th ICALP, Lecture Notes in Computer Science 267, Springer-Verlag, NY (1987), 386\u2013393."},{"key":"4_CR18","first-page":"49","volume":"3","author":"S. Radziszowski","year":"1988","unstructured":"S. Radziszowski and D. Kreher, Solving subset sum problems with the L 3 algorithm, J. Combin. Math. Combin. Comput. 3 (1988), 49\u201363.","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C. P. Schnorr","year":"1987","unstructured":"C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science 53 (1987), 201\u2013224.","journal-title":"Theoretical Computer Science"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0196-6774(88)90004-1","volume":"9","author":"C. P. Schnorr","year":"1988","unstructured":"C. P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), 47\u201362.","journal-title":"J. Algorithms"},{"key":"4_CR21","unstructured":"C. P. Schnorr and M. Euchner, Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, Proceedings of Fundamentals of Computation Theory\u2019 91, to be published."},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"M. Seysen, Simultaneous reduction of a lattice basis and its reciprocal basis, Combinatorica, to appear.","DOI":"10.1007\/BF01202355"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 EUROCRYPT \u201991"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46416-6_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:11:32Z","timestamp":1605647492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46416-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540546207"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-46416-6_4","relation":{},"subject":[]}}