Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach

Antoine Joux, Karol Węgrzycki

Lagarias and Odlyzko (J.~ACM~1985) proposed a polynomial time algorithm for solving ``\emph{almost all}'' instances of the Subset Sum problem with $n$ integers of size $Ω(Γ_{\text{…