On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

DOI10.1137/0215038zbMath0592.94010DBLPjournals/siamcomp/Frieze86OpenAlexW2070268091WikidataQ57401632 ScholiaQ57401632MaRDI QIDQ3722413

Alan M. 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

cryptographyanalysis of algorithmsrandom problemslattice algorithm

Mathematics Subject Classification ID

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

Related Items (11)

Lattice basis reduction: Improved practical algorithms and solving subset sum problems ⋮ Tightly secure signatures from lossy identification schemes ⋮ Lattice points in high-dimensional spheres ⋮ Safer parameters for the Chor-Rivest cryptosystem ⋮ Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ Improved low-density subset sum algorithms ⋮ Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme ⋮ Random knapsack in expected polynomial time ⋮ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum ⋮ Tightly secure signature schemes from the LWE and subset sum assumptions

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