caa a22 4500 469034025 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920601xx s 000 0 eng 10.1007/BF01201999 doi (NATIONALLICENCE)springer-10.1007/BF01201999 Improved low-density subset sum algorithms [Elektronische Daten] [Matthijs Coster, Antoine Joux, Brian LaMacchia, Andrew Odlyzko, Claus-Peter Schnorr, Jacques Stern] The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on basis reduction algorithms to find short non-zero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density<0.6463 ... in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This paper presents two modifications of that algorithm, either one of which would solve almost all problems of density<0.9408 ... if it could find shortest non-zero vectors in lattices. These modifications also yield dramatic improvements in practice when they are combined with known lattice basis reduction algorithms. Birkhäuser Verlag, 1992 subset sum problems nationallicence knapsack cryptosystems nationallicence lattices nationallicence lattice basis reduction nationallicence 11Y16 nationallicence Coster Matthijs AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Joux Antoine Ecole Normale Supérieure, 45 rue d'Ulm, 75230, Paris Cedex 05, France aut LaMacchia Brian AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Odlyzko Andrew AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Schnorr Claus-Peter Fachbereich Mathematik/Informatik, Universität Frankfurt, Postfach 11 19 32, 6000, Frankfurt am Main, Germany aut Stern Jacques Ecole Normale Supérieure, 45 rue d'Ulm, 75230, Paris Cedex 05, France aut computational complexity Birkhäuser-Verlag 2/2(1992-06-01), 111-128 1016-3328 2:2<111 1992 2 37 https://doi.org/10.1007/BF01201999 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01201999 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Coster Matthijs AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Joux Antoine Ecole Normale Supérieure, 45 rue d'Ulm, 75230, Paris Cedex 05, France aut NATIONALLICENCE 700 1- LaMacchia Brian AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Odlyzko Andrew AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Schnorr Claus-Peter Fachbereich Mathematik/Informatik, Universität Frankfurt, Postfach 11 19 32, 6000, Frankfurt am Main, Germany aut NATIONALLICENCE 700 1- Stern Jacques Ecole Normale Supérieure, 45 rue d'Ulm, 75230, Paris Cedex 05, France aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/2(1992-06-01), 111-128 1016-3328 2:2<111 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer