TY  - JOUR
A1  - Coster, Matthijs J.
A1  - Joux, Antoine
A1  - LaMacchia, Brian A.
A1  - Odlyzko, Andrew M.
A1  - Schnorr, Claus Peter
A1  - Stern, Jacques
T1  - Improved low-density subset sum algorithms
N2  - 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 nonzero 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.
KW  - subset sum problems
KW  - knapsack cryptosystems
KW  - lattices
KW  - lattice basis reduction
Y1  - 2005
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4281
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-12044
SN  - 1016-3328
SN  - 1420-8954
N1  - Erschienen in: Computational complexity, 2.1992, Nr. 2, S. 111-128
SP  - 1
EP  - 16
ER  -