Improved Low-Density Subset Sum Algorithms (1991)

Content Provider	CiteSeerX
Author	Odlyzko, Andrew M. Schnorr, Claus-Peter Coster, Matthijs Lamacchia, Brian A. Stern, Jacques Joux, Antoine
Abstract	. 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. Key words. subset sum problems; knapsack cryptosystems; lattices; lattice basis reduction. Subject classifications. 1...
File Format	PDF
Journal	COMPUTATIONAL COMPLEXITY
Journal	Computational Complexity
Publisher Date	1991-01-01
Access Restriction	Open
Subject Keyword	Subject Classification Special Lattice Subset Sum Problem Polynomial-time Algorithm Low-density Subset Sum Algorithm Low Density Lagarias-odlyzko Algorithm Sum Problem Basis Reduction Short Non-zero Vector General Subset Sum Problem Shortest Non-zero Vector Known Lattice Basis Reduction Algorithm Basis Reduction Algorithm Dramatic Improvement Polynomial Time Non-zero Vector
Content Type	Text
Resource Type	Article