An improved low-density subset sum algorithm

M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

57 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 note shows that a simple modification of that algorithm would solve almost all problems of density < 0.9408 … if it could find shortest non-zero vectors in lattices. This modification also yields dramatic improvements in practice when it is combined with known lattice basis reduction algorithms.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology—EUROCRYPT 1991 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings
EditorsDonald W. Davies
PublisherSpringer Verlag
Pages54-67
Number of pages14
ISBN (Print)9783540546207
DOIs
StatePublished - 1991
EventWorkshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991 - Brighton, United Kingdom
Duration: Apr 8 1991Apr 11 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume547 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherWorkshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991
CountryUnited Kingdom
CityBrighton
Period4/8/914/11/91

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

Cite this