TY - INPR
A1 - Schnorr, Claus Peter
A1 - Euchner, Martin
T1 - Lattice basis reduction : improved practical algorithms and solving subset sum problems
N2 - We report on improved practical algorithms for lattice basis reduction. We propose a practical floating point version of theL3-algorithm of Lenstra, Lenstra, Lovász (1982). We present a variant of theL3-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 to 66 random weights of arbitrary bit length within at most a few hours on a UNISYS 6000/70 or within a couple of minutes on a SPARC1 + computer.
KW - Lattice basis reduction
KW - LLL-reduction
KW - Korkin—Zolotarev reduction
KW - Block Korkin—Zolotarev reduction
KW - Shortest lattice vector problem
KW - Subset sum problem
KW - Low density subset sum algorithm
KW - Knapsack problem
KW - Stable reduction algorithm
Y1 - 1993
UR - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4259
UR - https://nbn-resolving.org/urn:nbn:de:hebis:30-12296
SN - 1436-4646
SN - 0025-5610
N1 - Erschienen in: Mathematical programming, 66.1994, Nr. 1-3, S. 181-199, doi:10.1007/BF01581144
SP - 1
EP - 27
ER -