{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T12:58:09Z","timestamp":1772283489389,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01201999","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T13:26:08Z","timestamp":1109251568000},"page":"111-128","source":"Crossref","is-referenced-by-count":157,"title":["Improved low-density subset sum algorithms"],"prefix":"10.1007","volume":"2","author":[{"given":"Matthijs J.","family":"Coster","sequence":"first","affiliation":[]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[]},{"given":"Brian A.","family":"LaMacchia","sequence":"additional","affiliation":[]},{"given":"Andrew M.","family":"Odlyzko","sequence":"additional","affiliation":[]},{"given":"Claus-Peter","family":"Schnorr","sequence":"additional","affiliation":[]},{"given":"Jacques","family":"Stern","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","series-title":"Proceedings of Crypto '83","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-1-4684-4730-9_2","volume-title":"Advances in Cryptology","author":"E. F. Brickell","year":"1984","unstructured":"E. F. Brickell, Solving low density knapsacks, inAdvances in Cryptology, Proceedings of Crypto '83, Plenum Press, New York, 1984, 25?37."},{"key":"CR2","unstructured":"E. F. Brickell, The cryptanalysis of knapsack cryptosystems, inApplications of Discrete Mathematics, R. D. Ringeisen and F. S. Roberts, eds., SIAM, 1988, 3?23."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1109\/5.4443","volume":"76","author":"E. F. Brickell","year":"1988","unstructured":"E. F. Brickell andA. M. Odlyzko, Cryptanalysis: a survey of recent results,Proc. IEEE 76 (1988), 578?593.","journal-title":"Proc. IEEE"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1109\/18.21214","volume":"34","author":"B. Chor","year":"1988","unstructured":"B. Chor andR. Rivest, A knapsack-type public key cryptosystem based on arithmetic in finite fields,IEEE Trans. Information Theory IT-34 (1988), 901?909.","journal-title":"IEEE Trans. Information Theory IT"},{"key":"CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/3-540-46416-6_4","volume-title":"Advances in Cryptology: Proceedings of Eurocrypt '91","author":"M. J. Coster","year":"1991","unstructured":"M. J. Coster, B. A. LaMacchia, A. M. Odlyzko andC.-P. Schnorr, An improved low-density subset sum algorithm, inAdvances in Cryptology: Proceedings of Eurocrypt '91, D. W. Davies, ed.,Lecture Notes in Computer Science 547, Springer-Verlag, New York, 1991, 54?67."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/978-94-009-2794-0_7","volume-title":"Performance Limits in Communication, Theory and Practice","author":"Y. Desmedt","year":"1988","unstructured":"Y. Desmedt, What happened with knapsack cryptographic schemes?, inPerformance Limits in Communication, Theory and Practice, J. K. Skwirzynski, ed., Kluwer, Boston, 1988, 113?134."},{"key":"CR7","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":"CR8","doi-asserted-by":"crossref","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) (1986), 536?539.","journal-title":"SIAM J. Comput."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/0218037","volume":"18","author":"M. L. Furst","year":"1989","unstructured":"M. L. Furst andR. Kannan, Succinct certificates for almost all subset sum problems,SIAM J. Comput. 18 (1989), 550?558.","journal-title":"SIAM J. Comput."},{"key":"CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey andD. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, 1979."},{"issue":"5","key":"CR11","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, andC.-P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers,SIAM J. Comput. 18(5) (1989), 859?881.","journal-title":"SIAM J. Comput."},{"key":"CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/3-540-54458-5_70","volume-title":"Proceedings of Fundamentals of Computation Theory '91","author":"A. Joux","year":"1991","unstructured":"A. Joux andJ. Stern, Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems,Proceedings of Fundamentals of Computation Theory '91, L. Budach, ed.,Lecture Notes in Computer Science 529, Springer-Verlag, New York, 1991, 258?264."},{"issue":"1","key":"CR13","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"J. C. Lagarias","year":"1985","unstructured":"J. C. Lagarias andA. M. Odlyzko, Solving low-density subset sum problems,J. Assoc. Comp. Mach. 32(1) (1985), 229?246.","journal-title":"J. Assoc. Comp. Mach."},{"key":"CR14","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. Also available as AI Technical Report 1283, MIT Artificial Intelligence Laboratory, Cambridge, MA, 1991."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra, andL. Lov\u00e1sz, Factoring polynomials with rational coefficients,Math. Ann. 261 (1982), 515?534.","journal-title":"Math. Ann."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01571276","volume":"110","author":"J. E. Mazo","year":"1990","unstructured":"J. E. Mazo andA. M. Odlyzko, Lattice points in high-dimensional spheres,Monatsh. Math. 110 (1990), 47?61.","journal-title":"Monatsh. Math."},{"key":"CR17","series-title":"Proc. Symp. Appl. Math.","first-page":"75","volume-title":"Cryptology and Computational Number Theory","author":"A. M. Odlyzko","year":"1990","unstructured":"A. M. Odlyzko, The rise and fall of knapsack cryptosystems, inCryptology and Computational Number Theory, C. Pomerance, ed.,Proc. Symp. Appl. Math. 42, Amer. Math. Soc., Providence, 1990, 75?88."},{"key":"CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/3-540-18088-5_33","volume-title":"Automata, Languages, and Programming: 14th ICALP","author":"A. Paz","year":"1987","unstructured":"A. Paz andC.-P. Schnorr, Approximating integer lattices by lattices with cyclic factor groups, inAutomata, Languages, and Programming: 14 th ICALP,Lecture Notes in Computer Science 267, Springer-Verlag, New York, 1987, 386?393."},{"key":"CR19","first-page":"49","volume":"3","author":"S. Radziszowski","year":"1988","unstructured":"S. Radziszowski andD. Kreher, Solving subset sum problems with theL 3 algorithm,J. Combin. Math. Combin. Comput. 3 (1988), 49?63.","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"CR20","doi-asserted-by":"crossref","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?224.","journal-title":"Theoretical Computer Science"},{"key":"CR21","doi-asserted-by":"crossref","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?62.","journal-title":"J. Algorithms"},{"key":"CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/3-540-54458-5_51","volume-title":"Proceedings of Fundamentals of Computation Theory '91","author":"C.-P. Schnorr","year":"1991","unstructured":"C.-P. Schnorr andM. Euchner, Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, inProceedings of Fundamentals of Computation Theory '91, L. Budach, ed.,Lecture Notes in Computer Science 529, Springer-Verlag, New York, 1991, 68?85."},{"key":"CR23","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":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01201999.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01201999\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01201999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T17:01:40Z","timestamp":1556730100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01201999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01201999"],"URL":"https:\/\/doi.org\/10.1007\/bf01201999","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}