Accelerated Slide- and LLL-Reduction.
Claus-Peter Schnorr · Electronic colloquium on computational complexity · 2011
Given an LLL-basis B of dimension n = hk we accelerate slide-reduction with blocksize k to run under a reasonable assumption within 1 6 nh log1+e α local SVP-computations of dimension k, where α ≥ 4 3 measures the quality of the given LLL-basis and e is the quality of slidereduction. If the given basis B is already slide-reduced for blocksize k/2 the 1 6 nh log1+e α bound further decreases to 2 3 h(1 + log1+e γk/2). This bound is polynomial in n for arbitrary bit-length of B, it improves previous bounds considerably. We also accelerate LLL-reduction.