Improved low-density subset sum algorithms

Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus Peter Schnorr, Jacques Stern

Research output: Contribution to journalArticlepeer-review

148 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)111-128
Number of pages18
JournalComputational Complexity
Volume2
Issue number2
DOIs
StatePublished - Jun 1992

Keywords

  • Subject classifications: 11Y16
  • knapsack cryptosystems
  • lattice basis reduction
  • lattices
  • subset sum problems

Fingerprint Dive into the research topics of 'Improved low-density subset sum algorithms'. Together they form a unique fingerprint.

Cite this