TY  - JOUR
A1  - Schnorr, Claus Peter
T1  - A hierarchy of polynomial time lattice basis reduction algorithms
T2  - Theoretical Computer Science
N2  - We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn are integral and have the length bound B. This algorithm successively applies Korkine–Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.
Y1  - 2023
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/75886
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-758869
SN  - 0304-3975
VL  - 53
IS  - 2-3
SP  - 201
EP  - 224
PB  - Elsevier
CY  - Amsterdam [u.a.]
ER  -