Lattice basis reduction: Improved practical algorithms and solving subset sum problems

We report on improved practical algorithms for lattice basis reduction. We propose a practical floating point version of theL 3-algorithm of Lenstra, Lenstra, Lovász (1982). We present a variant of theL 3-algorithm with “deep insertions” and a practical algorithm for block Korkin—Zolotarev reduction, a concept introduced by Schnorr (1987). Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up...