Improved low-density subset sum algorithms
type: Item
instance of: scholarly article
title: Improved low-density subset sum algorithms
zbMATH Open document ID: 0768.11049
DOI: 10.1007/BF01201999
author: Matthijs J. Coster
author: Antoine Joux
author: B. A. LaMacchia
author: Jacques Stern
author: Andrew Odlyzko
author: Claus Peter Schnorr
published in: Computational Complexity
publication date: 1993-04-01T00:00:00Z
review text: The authors improve an algorithm of \textit{J. C. Lagarias} and \textit{A. M. Odlyzko} [J. Assoc. Comput. Mach. 32, 229-246 (1985)] which reduces the solution of a subset sum problem to the calculation of a shortest vector in a suitable lattice. The authors introduce two new lattices the use of which yields solutions for all subset sum problems of density \(< 0.9408\) (thus improving the old bound 0.6463 of Lagarias and Odlyzko).
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 149534
zbMATH Keywords: subset sum algorithms
zbMATH Keywords: Lagarias-Odlyzko algorithm
zbMATH Keywords: knapsack cryptosystems
zbMATH Keywords: lattices
zbMATH Keywords: lattice basis reduction
reviewed by: Michael E. Pohst
MaRDI profile type: Publication
cites work: Cryptanalysis: a survey of recent results
cites work: A knapsack-type public key cryptosystem based on arithmetic in finite fields
cites work: An Improved Low-Density Subset Sum Algorithm
cites work: On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
cites work: Succinct Certificates for Almost All Subset Sum Problems
cites work: Q4198056
cites work: Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
cites work: Q4266536
cites work: Solving low-density subset sum problems
cites work: Factoring polynomials with rational coefficients
cites work: Lattice points in high-dimensional spheres
cites work: Q3806990
cites work: A hierarchy of polynomial time lattice basis reduction algorithms
cites work: A more efficient algorithm for lattice basis reduction
cites work: Q4266548
cites work: Simultaneous reduction of a lattice basis and its reciprocal basis
full work available at URL: https://doi.org/10.1007/bf01201999
OpenAlex ID: W1968182591
description: scientific article; zbMATH DE number 149534