2026-07-21T14:15:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25546 2026-03-19T13:34:48Z ddc:004 open_access

Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach Joux, Antoine Węgrzycki, Karol Average-Case Analysis Subset Sum Lattice Reduction LLL Lagarias and Odlyzko (J.ACM 1985) proposed a polynomial-time algorithm for solving "almost all" instances of the Subset Sum problem with n integers of size Ω(Γ_LO), where log₂(Γ_LO) > n² log₂(γ) and γ is a parameter of the lattice basis reduction (γ > √{4/3} for LLL). The algorithm of Lagarias and Odlyzko is a cornerstone of cryptography. However, the theoretical guarantee on the density of feasible instances has remained unimproved for almost 40 years. In this paper, we propose an algorithm that solves "almost all" instances of Subset Sum with integers of size Ω(√{Γ_LO}) after a single call to lattice reduction. Additionally, our approach allows solving the Subset Sum problem for multiple targets, whereas the previous method could handle only one target per call to lattice basis reduction. We introduce a modular arithmetic approach to the Subset Sum problem, leveraging lattice reduction to solve a linear system modulo a suitably large prime. By analyzing the lengths of the LLL-reduced basis vectors of both the primal and dual lattices simultaneously, we show that density guarantees can be improved. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Joux and Karol Węgrzycki 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.57 urn:nbn:de:0030-drops-255462 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.57 eng https://creativecommons.org/licenses/by/4.0/legalcode