We accelerate the slide-reduction algorithm of [GN08] with blocksize k to run for a given LLL-basis B of dimension n= hk under reasonable assumptions within \ $\frac14\, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \ local SVP-computations of dimension k, where $\alpha \ge \frac 43$ is the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize k/2 the $\frac14 \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ bound further decreases to $ nh^2(1 +\log_{1+\varepsilon} \gamma_{k/2})$, where $\gamma_{k/2}$ is the Hermite constant.
These bounds are polynomial in $n$ for arbitrary bit-length of $B$. Slide-reduced bases for which the approximation factor $\|\mathbf{b}_1\|/\lambda_1$ is nearly maximal can easily be improved. If $\|\mathbf{b}_1\|/\lambda_1 = \gamma_k^{\frac{n-k}{k-1}}$ is maximal we can easily find a shortest lattice vector. We also accelerate LLL-reduction.\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.

We add in Theorem 4 and Theorem 5 a fast method to improve slide-reduced bases for $k$ and $\varepsilon =0$ which maximize approximation factor $\|\mathbf{b}_1\|/\lambda_1$. A shortest lattice vector can easily be found for such worst case slide-reduced bases. For LLL-bases with $\delta =1$ this finds a shortest lattice vector in $n^2$ arithmetic steps, see Theorem 5.

On page 3 we correct the sum $ \sum_{\ell =1}^{h-1} h\ell -\ell^2 =
\frac {h^3-h}{6}$ which was wrongly written as $\sum_{\ell =1}^{h-1} h\ell -\ell^2 = \frac {h^3-h^2 -h}{6}$

We accelerate the slide-reduction algorithm of [GN08] with blocksize $k$ to run for a given LLL-basis $B$ of dimension $n= hk$ under reasonable assumptions within \ $\frac14\, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations of dimension $k$, where $\alpha \ge \frac 43$ is the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ the $\frac14 \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ bound
further decreases to $ nh^2(1 + \log_{1+\varepsilon} \gamma_{k/2})$, where $\gamma_{k/2}$ is the Hermite constant. These bounds are polynomial in $n$ for arbitrary bit-length of $B$. We also accelerate LLL-reduction.

We describe the algorithms ASR for accelerated almost slide reduction and ALR for accelerated LLL-reduction more explicitely. The notion of almost slide reduced basis, (asr-basis) has been slightly modified to simplify the proofs of the theorems. We indicate how to extend the algorithms to the case of highest quality where epsilon =0 so that the polynomial time bounds are preserved

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.

In the proof of Theorem 2at one point the exponent h-2\ell -1 of (\mathcal+\ell/\mathcal{D}_\ell+1) was missing and has been inserted.
Some proofs have been updated for better readability.
The integer m associated to ASR and ALR has been replaced by two different integers \mu and \bar{\mu} which enter the analysis.

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.

misprint in reference [S06]

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \ local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.}

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.

The paragraph Time bound compared to[GN08] on page 3
has been revised

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.

The reference [HPS11]has been added

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assumption in \ $\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \ local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$ measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.

the misprint "assjmption" in the abstract is corrected to assumption

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.