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

Analysis of algorithms and problem complexity (68Q25) Finite fields and commutative rings (number-theoretic aspects) (11T99) 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

(19)

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

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)