## 1 Introduction
### Definitions of Reduced Lattice Bases  
Without loss of generality we assume that \(b_{1},\ldots,b_{n}\) are linearly independent. Superscript \(t\) is used to denote the transpose of a vector or a matrix. The \(l_{2}\) norm is given by \(\|y\|=(yy^{t})^{0.5}\). \([x]\) denotes the nearest integer to a real number \(x\) (if non-unique then choose the candidate with smallest magnitude), \(\lceil x\rceil\) denotes the smallest integer greater than or equal to \(x\), and \(\lfloor x\rfloor\) denotes the largest integer less than or equal to \(x\). \(T_{i,j}\) is the entry at the \(i\)-th row and \(j\)-th column of a matrix T. We use \(I\) to represent an identity matrix, and \(e_{i}\) to represent its \(i\)-th column. Let \(B\in\mathbb{Z}^{n\times d}\) be such that the \(i\)-th row of \(B\) is given by \(b_{i}\) for \(1\leq i\leq n\). For a given lattice basis \(b_{1},\ldots,b_{n}\) the Gram-Schmidt algorithm determines the associated orthogonal vectors \(b_{1}^{*},\ldots,b_{n}^{*}\) together with coefficients \(\Gamma_{j,i}(1\leq j<i\leq n)\) defined inductively by  
\[b_{i}^{*}=b_{i}-\sum_{j=1}^{i-1}\Gamma_{j,i}b_{j}^{*},\ \ \mathrm{where}\ \Gamma_{j,i}=b_{j}^{*}b_{i}^{t}/\|b_{j}^{*}\|^{2} \tag{1.1}\]  
This can be rewritten as \(B=\Gamma^{t}B^{*}\), where \(B^{*}\) denotes the matrix whose \(i\)-th row is \(b_{i}^{*}\), and \(\Gamma\) is a upper triangular matrix with \(\Gamma_{i,i}=1\) and \(\Gamma_{j,i}\) (\(j<i\)) is given in (1.1). Let \(D_{i,\ldots,j}:=\|b_{i}^{*}\|^{2}\cdots\|b_{j}^{*}\|^{2}\). We denote \(D_{1,\ldots,l}\) by \(d_{l}\). Note that \(d_{n}\) is the Gramian determinant of \(B\). When we are considering \(k\) segments of \(B\) and \(B^{*}\), \(D_{k(l-1)+1,\ldots,kl}:=\|b_{k(l-1)+1}^{*}\|^{2}\cdots\|b_{kl}^{*}\|^{2}\) is the segment Gramian determinant, and for simplicity we denote it by \(D(l)\), where \(k\) is fixed. 1. A basis is called _size-reduced_ if \(|\Gamma_{j,i}|\leq 1/2\) for \(1\leq j<i\leq n\). The notion of a size reduced basis goes back to [PERSON] [12]. 2. A basis is called (\(\delta\),\(\eta\))-_reduced_ if \((\delta-\Gamma_{i,i+1}^{2})\|b_{i}^{*}\|^{2}\leq\|b_{i+1}^{*}\|^{2}\) for \(i=1,\ldots,n-1\), \(\delta\in(\frac{1}{4},1]\), \(|\Gamma_{j,i}|\leq\eta\), \(\eta\in[1/2,\sqrt{\delta})\). For \(\delta=\frac{3}{4}\) and \(|\Gamma_{j,i}|\leq 1/2\) it is called _2-reduced_ because the above inequality becomes \(\|b_{i}^{*}\|^{2}\leq 2\|b_{i+1}^{*}\|^{2}\). A basis is called \(\delta\)-_LLL reduced_ if it is _size-reduced_ and \(\delta\)-_reduced_. It is simply called _LLL reduced_ if it is _size-reduced_ and _2-reduced_. The LLL reduced basis was introduced by [PERSON], [PERSON], and [PERSON] [7]. * A basis is called _semi-reduced_ if it is _size-reduced_ and satisfies weaker conditions \(\|b_{i}^{*}\|^{2}\leq 2^{n}\|b_{i+1}^{*}\|^{2}\;\;\;\mbox{for}\;\;i=1,\ldots,n-1\). * A basis is called _Korkine-Zolotarev basis_ if it is _size-reduced_ and if \(\|b_{i}^{*}\|=\lambda_{1}(L_{i})\) for \(i=1,\ldots,n,\) where \(L_{i}\) is the orthogonal projection of \(L\) on the orthogonal complement of \(span\{b_{1},\ldots,b_{i-1}\}\). The concepts of block reduced and segment reduced basis are defined by dividing a basis into \(k\) blocks or segments, _i.e._, \(n=mk\), and then specifying appropriate conditions on basis vectors within each block and among blocks. * A basis \(b_{1},\ldots,b_{mk}\) is called _Block KZ reduced basis_ if it is _size-reduced_ and if the projections of all \(2k\)-blocks \(b_{ik+1},\ldots,b_{(i+2)k}\) on the orthogonal complement of \(span\{b_{1},\ldots,b_{ik}\}\) for \(i=0,\ldots,m-2\) are Korkine-Zolotarev reduced. * A basis \(b_{1},\ldots,b_{mk}\) is called _\(k\)-segment LLL reduced_ if the following conditions hold. * It is size-reduced. * \((\delta-\Gamma_{i,i+1}^{2})\|b_{i}^{*}\|^{2}\leq\|b_{i+1}^{*}\|^{2}\;\;\mbox{ for}\;\;i\
eq kl\), \(l\in\mathbb{Z}\), i.e., vectors within each segment of the basis are \(\delta\)-_reduced_, and
* Letting \(\alpha:=1/(\delta-\frac{1}{4})\), two successive segments of the basis are connected by the following two conditions.