An improved low-density subset sum algorithm (Q4037449)

[For the entire collection see Zbl 0756.00008.] Given positive integers \(a_ 1,\dots,a_ n\), \(s\) the knapsack or subset sum problem is to find \(e_ 1,\dots,e_ n\in\{0,1\}\) such that \(\sum_{i=1}^ n e_ i a_ i=s\). This is an NP-complete problem and therefore used in developing some cryptosystems; however almost all of these have been broken by now. There are algorithms e.g. by \textit{J. C. Lagarias} and \textit{A. M. Odlyzko} [J. ACM 32, 229--246 (1985; Zbl 0632.94007)] which show that almost all low-density sum problems can be solved in polynomial time. The density is defined by \(d=n/\log_ 2 \max_{1\leq i\leq n} a_ i\), and the interesting case for cryptosystems is \(d\leq 1\). The Lagarias-Odlyzko algorithm is useful only for \(d<0,6463\dots\), and in this paper a modification of the algorithm is given increasing the bound for \(d\) to 0,9408\dots\ .