On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

DOI10.1137/0215038MaRDI QIDQ3722413zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alan Frieze

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215038

zbMATH Keywords

analysis of algorithmscryptographylattice algorithmrandom problems

Mathematics Subject Classification ID

Finite fields and commutative rings (number-theoretic aspects) (11T99) Analysis of algorithms and problem complexity (68Q25) Communication, information (94A99)

Recommendations

• An Improved Low-Density Subset Sum Algorithm
• scientific article; zbMATH DE number 176777
• Solving low-density subset sum problems
• Improved low-density subset sum algorithms
• Solving dense subset-sum problems by using analytical number theory

Cited in

(21)

• The bounded subset sum problem is almost everywhere randomly decidable in O(n)
• Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations
• Improved low-density subset sum algorithms
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• The \(k\)-subset sum problem over finite fields
• Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme
• Tightly secure signature schemes from the LWE and subset sum assumptions
• Safer parameters for the Chor-Rivest cryptosystem
• Lattice points in high-dimensional spheres
• Tightly secure signatures from lossy identification schemes
• Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
• A short note on Merlin-Arthur protocols for subset sum
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
• Succinct Certificates for Almost All Subset Sum Problems
• scientific article; zbMATH DE number 1058053 (Why is no real title available?)
• Some results on an encryption method using subset-sums of pseudo-recursive sequences
• Random knapsack in expected polynomial time
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• Algebraic algorithms for variants of subset sum
• Subset-optimized BLS multi-signature with key aggregation
• On the MCMC performance in Bernoulli group testing and the random max-set cover problem

This page was built for publication: On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3722413)