## 1 Introduction
### Discussion on Various Reduced Bases  
The ratios \(\frac{\|b_{i}\|^{2}}{\lambda_{i}^{2}},i=1,\ldots,n\) are used to measure the quality of various reduced bases defined above. We call these approximation ratios. Known bounds on approximation ratios for various reduced bases, known algorithms for generating them, the worst case running time of these algorithms, and the bit-precision used in performing the computations (addition, subtraction, multiplication and division) in these algorithms are summarized in Table 1. The bounds in this table assume \(k=O(\sqrt{n})\), and \(d=O(n)\). Following [7, 8] we use \(M_{sc}:=\max\{2^{n},M_{0},d_{1},\ldots,d_{n}\}\), where \(M_{0}:=\max_{i=1,\ldots,n}\|b_{i}\|^{2}\) to measure the complexity of these algorithms. Note that \(M_{sc}=2^{O(n^{2})}\) when \(\|b_{i}\|=2^{O(n)}\). The work of [PERSON], [PERSON], and [PERSON] [7] is seminal on finding a reduced lattice basis, and its implication on the problem of finding successive minima. Their algorithm for finding an LLL reduced basis is polynomial time. In particular, for \(M_{sc}=2^{O(n^{2})}\) in the worst case it requires \(O(n^{5})\) arithmetic operations using \(O(n^{2})\) bit numbers. Since the development of the LLL algorithm significant effort has been directed towards developing methods for finding an improved quality basis in polynomial time, and finding a worse quality basis with a better worst case computational complexity. Research has also progressed towards generalizing the LLL algorithm to arbitrary norms [18, 19]. The algorithm by [PERSON] [8] finds a semi-reduced basis. It requires \(O(n)\) less time over the LLL algorithm. However, the bounds on the approximation ratios for a semi-reduced basis are of a significantly lower quality. A better complexity for finding a semi-reduced basis is also proved by [PERSON] [14]. [PERSON] [9] proposes an algorithm for finding Korkine-Zolotarev (KZ) basis that runs in \(O(n^{O(n)}\ln M_{0})\) arithmetic operations on \(O(n^{2}\ln M_{0})\) bit integers. [PERSON]'s algorithm uses the LLL algorithm as a black box. This bound for finding a KZ basis is improved by [PERSON] [10] to \(O(n^{n/2+o(n)}+n^{4}\ln M_{0})\) arithmetic operations using \(O(n\ln M_{0})\) bit integers. The bound for [PERSON]'s algorithm in Table 1 is given for performing a KZ reduction of a block of size \(2k\). [PERSON] [10] further introduces the notion of a _semi block 2k reduced_ basis, and uses this concept to show that a \(O(k^{(n/k)})\)-approximate shortest vector is found in \(O(n^{2}(k^{k/2+o(k)}+n^{2})\ln(M_{0}))\) arithmetic operation using \(O(n\ln M_{0})\) bit integers. This leads to a hierarchy of algorithms for finding the shortest lattice vector, and a semi block 2k reduced basis. The complexity in Table 1 is a special case where \(k=\lfloor 2\sqrt{n}\rfloor\). [PERSON] and [PERSON] [20] propose the concept of a segment reduced basis, and give an algorithm for finding such a basis. Similar to the semi-reduction algorithm of [PERSON] [8] the segment reduction algorithm works with a subset of vectors in the lattice basis at a time. However, it worsens the approximation ratios only slightly, and in a controllable fashion. Moreover, it also achieves an \(O(n)\) reduction in the worst case complexity over the LLL algorithm. Since the writing of the original draft of this paper improvements in computational complexity of the LLL and segment LLL algorithms have also been achieved by showing that the methods can be modified to perform computations using \(O(n)\) bit floating point numbers. In particular, [PERSON] and [PERSON] [16] rearranged computations in the Cholesky factorization algorithm and used [PERSON]'s nearest point algorithm to update the Cholesky factor coefficients to show that the LLL-algorithm can be correctly implemented with \(O(n)\) bit floating point precision computations.