Improved low-density subset sum algorithms

  • 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.

Download full text files

Export metadata

Metadaten
Author:Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus Peter SchnorrGND, Jacques Stern
URN:urn:nbn:de:hebis:30-12044
ISSN:1016-3328
ISSN:1420-8954
Document Type:Article
Language:English
Date of Publication (online):2005/07/01
Year of first Publication:1992
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2005/07/01
Tag:knapsack cryptosystems; lattice basis reduction; lattices; subset sum problems
Page Number:16
First Page:1
Last Page:16
Note:
Erschienen in: Computational complexity, 2.1992, Nr. 2, S. 111-128
Source:Auch in: Computational Complexity 2, 1992 ,2,S.111-128 http://www.mi.informatik.uni-frankfurt.de/research/papers.html
HeBIS-PPN:186979134
Institutes:Informatik und Mathematik / Mathematik
Informatik und Mathematik / Informatik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Classification:11-XX NUMBER THEORY / 11Yxx Computational number theory [See also 11-04] / 11Y16 Algorithms; complexity [See also 68Q25]
Licence (German):License LogoDeutsches Urheberrecht

OPUS4 Logo