Welcome to the resource topic for
**2012/620**

**Title:**

Solving Subset Sum Problems of Densioty close to 1 by “randomized” BKZ-reduction

**Authors:**
Claus P. Schnorr, Taras Shevchenko

**Abstract:**

Subset sum or Knapsack problems of dimension n are known to be hardest for knapsacks of density close to 1.These problems are NP-hard for arbitrary n. One can solve such problems either by lattice basis reduction or by optimized birthday algorithms. Recently Becker, Coron, Jou } [BCJ10] present a birthday algorithm that follows Schroeppel, Shamir [SS81], and Howgrave-Graham, Joux [HJ10]. This algorithm solves 50 random knapsacks of dimension 80 and density close to 1 in roughly 15 hours on a 2.67 GHz PC. We present an optimized lattice basis reduction algorithm that follows Schnorr, Euchne} [SE03] using pruning of Schnorr, Hörner [SH95] that solves such random knapsacks of dimension 80 on average in less than a minute, and 50 such problems all together about 9.4 times faster and using much less space than [BCJ10] on another 2.67 GHz PC.

**ePrint:**
https://eprint.iacr.org/2012/620

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .