On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

Previous article Next article On the Lagarias-Odlyzko Algorithm for the Subset Sum ProblemA. M. FriezeA. M. Friezehttps://doi.org/10.1137/0215038PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractWe give a simple analysis of an algorithm for solving subset-sum problems proposed by Lagarias and Odlyzko [2].[1] R. Kannan, Improved algorithms for integer programming and related problems, Proc. 24th IEEE Symposium on Foundations of Computer Science, 1983 Google Scholar[2] J. C. Lagarias and , A. M. Odlyzko, Solving low density subset sum problems, Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, 1983, 1–10 Google Scholar[3] A. K. Lenstra, , H. W. Lenstra, Jr. and , L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515–534 84a:12002 0488.12001 CrossrefISIGoogle Scholar[4] R. C. Merkle and , M. E. Hellman, Hiding information and signatures in trap-door knapsacks, IEEE Trans. Inform. Theory, IT-24 (1978), 525–530 10.1109/TIT.1978.1055927 CrossrefISIGoogle Scholar[5] C. P. Shnorr, A hierarchy of polynomial time basis reduction algorithms, 1984, Proc. Symposium on the Theory of Algorithms, Pe'es, Hungary, to appear Google ScholarKeywordscomplexitylattice algorithmrandom problems Previous article Next article FiguresRelatedReferencesCited ByDetails Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation DetectionIEEE Transactions on Information Theory, Vol. 67, No. 12 | 1 Dec 2021 Cross Ref Tightly secure signature schemes from the LWE and subset sum assumptionsTheoretical Computer Science, Vol. 795 | 1 Nov 2019 Cross Ref High-Dimensional Linear Regression and Phase Retrieval via PSLQ Integer Relation Algorithm2019 IEEE International Symposium on Information Theory (ISIT) | 1 Jul 2019 Cross Ref Outsourced pattern matchingInternational Journal of Information Security, Vol. 17, No. 3 | 2 May 2017 Cross Ref Solutions of Hard Knapsack Problems Using Extreme PruningModern Discrete Mathematics and Analysis | 6 July 2018 Cross Ref A Review of Modern Cryptography: From the World War II Era to the Big-Data EraOptimization and Control for Systems in the Big-Data Era | 6 May 2017 Cross Ref Tightly Secure Signatures From Lossy Identification SchemesJournal of Cryptology, Vol. 29, No. 3 | 25 March 2015 Cross Ref Chosen-Ciphertext Security from Subset SumPublic-Key Cryptography – PKC 2016 | 18 February 2016 Cross Ref ReferencesInteger and Combinatorial Optimization | 22 August 2014 Cross Ref Outsourced Pattern MatchingAutomata, Languages, and Programming | 1 Jan 2013 Cross Ref Tightly-Secure Signatures from Lossy Identification SchemesAdvances in Cryptology – EUROCRYPT 2012 | 1 Jan 2012 Cross Ref Reticoli e crittografiaCrittografia nel Paese delle Meraviglie | 1 Jan 2012 Cross Ref Basis Reduction MethodsWiley Encyclopedia of Operations Research and Management Science | 14 January 2011 Cross Ref On the critical density associated with the matrix type knapsack cryptosystem2010 International Symposium On Information Theory & Its Applications | 1 Oct 2010 Cross Ref Public-Key Cryptographic Primitives Provably as Secure as Subset SumTheory of Cryptography | 1 Jan 2010 Cross Ref Safer parameters for the Chor–Rivest cryptosystemComputers & Mathematics with Applications, Vol. 56, No. 11 | 1 Dec 2008 Cross Ref The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum ProblemApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 1 Jan 2005 Cross Ref Solving Medium-Density Subset Sum Problems in Expected Polynomial TimeSTACS 2005 | 1 Jan 2005 Cross Ref Random knapsack in expected polynomial timeJournal of Computer and System Sciences, Vol. 69, No. 3 | 1 Nov 2004 Cross Ref The Shortest Vector in a Lattice is Hard to Approximate to within Some ConstantDaniele MicciancioSIAM Journal on Computing, Vol. 30, No. 6 | 27 July 2006AbstractPDF (282 KB)The Two Faces of Lattices in CryptologyCryptography and Lattices | 17 September 2001 Cross Ref Lattice Reduction in Cryptology: An UpdateAlgorithmic Number Theory | 1 Jan 2000 Cross Ref Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relationsComputers & Mathematics with Applications, Vol. 36, No. 6 | 1 Sep 1998 Cross Ref Probabilistic Analysis of AlgorithmsProbabilistic Methods for Algorithmic Discrete Mathematics | 1 Jan 1998 Cross Ref Efficient cryptographic schemes provably as secure as subset sumJournal of Cryptology, Vol. 9, No. 4 | 1 Sep 1996 Cross Ref Lattice basis reduction: Improved practical algorithms and solving subset sum problemsMathematical Programming, Vol. 66, No. 1-3 | 1 Aug 1994 Cross Ref Two notes on low-density subset sum algorithmAlgorithms and Computation | 3 June 2005 Cross Ref Improved low-density subset sum algorithmsComputational Complexity, Vol. 2, No. 2 | 1 Jun 1992 Cross Ref Lattice basis reduction: Improved practical algorithms and solving subset sum problemsFundamentals of Computation Theory | 9 June 2005 Cross Ref Improving the critical density of the Lagarias-Odlyzko attack against subset sum problemsFundamentals of Computation Theory | 9 June 2005 Cross Ref Lattice points in high-dimensional spheresMonatshefte für Mathematik, Vol. 110, No. 1 | 1 Mar 1990 Cross Ref An Algorithm Using Modular Arithmetic for the Subset Sum ProblemSystems and Computers in Japan, Vol. 21, No. 2 | 1 Jan 1990 Cross Ref Succinct Certificates for Almost All Subset Sum ProblemsMerrick L. Furst and Ravi KannanSIAM Journal on Computing, Vol. 18, No. 3 | 31 July 2006AbstractPDF (1000 KB)Cryptanalysis: a survey of recent resultsProceedings of the IEEE, Vol. 76, No. 5 | 1 May 1988 Cross Ref An Improved Low-Density Subset Sum AlgorithmAdvances in Cryptology — EUROCRYPT '91 Cross Ref Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration ApproachFrontiers in Algorithmics Cross Ref The shortest vector in a lattice is hard to approximate to within some constantProceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) Cross Ref Volume 15, Issue 2| 1986SIAM Journal on Computing317-627 History Submitted:24 April 1985Published online:13 July 2006 InformationCopyright © 1986 Society for Industrial and Applied MathematicsKeywordscomplexitylattice algorithmrandom problemsPDF Download Article & Publication DataArticle DOI:10.1137/0215038Article page range:pp. 536-539ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics