-
Available on Github
- Generated on Tue Jun 11 2019 15:21:27 for Lattice Tester Guide by
1.8.15
|
Lattice Tester Guide
1.0-9
Software Package For Testing The Uniformity Of Integral Lattices In The Real Space
|
This page contains a (not so brief) summary of the mathematical concepts used in LatticeTester.
The library is intended to ease the computation of uniformity measures (also called figures of merit) on lattices in the \(t\)-dimensional the real space \(\mathbb{R}^t\) that are contained in \(\mathbb{Z}^t\). We therefore introduce here exactly what those lattices are and part of the theory behind the implemented algorithms.
\(t\)- dimensional lattices in the real space \(\mathbb{R}^t\) are discrete subspaces of the real vector space \(\mathbb{R}^t\) that can be expressed as
\begin{equation} L_t = \left\{\mathbf{v} = \sum_{j=1}^t z_j\mathbf{v}_j\mid \mbox{ each } z_j\in\mathbb{Z}\right\} = \oplus_{j=1}^t \mathbb{Z} \mathbf{v}_j, \label {eq:lattice} \end{equation}
where \(t\) is a positive integer, and \(\mathbf{v}_1,\dots,\mathbf{v}_t\) are linearly independent vectors in \(\mathbb{R}^t\) which form a basis of the lattice. The matrix \(\mathbf{V}\), whose \(i\)th row is \(\mathbf{v}_i\), is the corresponding generator matrix of \(L_t\). A comprehensive treatment of such lattices can be found in [4]. The algorithms implemented in LatticeTester need to be exact most of the time. To work around this limitation, the library only considers lattices with \(\mathbf{v}_1,\dots,\mathbf{v}_t \in \mathbb{Z}^t\). Note that if the basis vectors are in \(\mathbb{Q}^t\) instead of \(\mathbb{Z}^t\) it is possible rescale the lattice by multiplying all the vectors it contains by an integer such that the resulting lattice is in \(\mathbb{Z}^t\). The details of this conversion are left to the user as it is not implemented.
The dual lattice of \(L_t^*\) is defined as
\[ L_t^* = \{\mathbf{h} \in \mathbb{R}^t \mid \forall \mathbf{v} \in L_t, \mathbf{h}\cdot\mathbf{v} \in \mathbb{Z} \}. \]
The dual of a given basis \(\mathbf{v}_1,\dots,\mathbf{v}_t\) is the set of vectors \(\mathbf{w}_1,\dots,\mathbf{w}_t\) in \(\mathbb{R}^t\) such that \(\mathbf{v}_i\cdot\mathbf{w}_j = \delta_{ij}\), where \(\delta_{ij}=1\) if \(i=j\), and \(\delta_{ij}=0\) otherwise. It forms a basis of the dual lattice. These \(\mathbf{w}_j\)'s are the columns of the dual basis generator matrix \(\mathbf{W} = \mathbf{V}^{-1}\), the inverse of the generator matrix \(\mathbf{V}\).
LatticeTester stores and manipulates only lattices by storing its basis and, possibly, its dual basis in integer coordinates. If a lattice has an integer basis, its dual is often fractional. This is a problem that is solved by storing a rescaled version of the dual: the m-dual \(mL_t^*\). When using the m-dual, m is chosen so that \(m\mathbf{W}\) is an integer matrix. Such a m usually is defined by the application for which lattices are used. It is the responsibility of the user to find it out. In this software and the documentation, we assume that the appropriate rescaling has already been done and we always work directly with a lattice \(\Lambda_t \subset \mathbb{Z}^t\) and its m-dual \(\Lambda_t^*\subset\mathbb{Z}^t\). The advantage of this framework is that all vector coordinates are integers and easily representable exactly on the computer.
There are a few more usefull definitions needed to understand this software. The determinant of the matrix \(\mathbf{V}\) is equal to the volume of the fundamental parallelepiped \(\{\mathbf{v} = \lambda_1\mathbf{v}_1 + \cdots + \lambda_t\mathbf{v}_t \mid 0\le \lambda_i\le 1\) for \(1\le i\le t\}\). It is independent of the choice of basis and is called the determinant or volume of \(L_t\). The quantity \(n = 1/\det(L_t) = 1/\det(\mathbf{V}) = \det(\mathbf{V}^{-1})\) is called the density of \(L_t\) and it represents the average number of points per unit of volume in the lattice. When \(L_t\) contains \(\mathbb{Z}^t\), the density \(n\) is an integer equal to the cardinality of the point set \(L_t \cap [0,1)^t\).
For a given lattice \(L_t\) and a subset of coordinates \(I = \{i_1,\dots,i_d\} \subseteq \{1,\dots,t\}\), denote by \(L_t(I)\) the projection of \(L_t\) over the \(d\)-dimensional subspace determined by the coordinates in \(I\). This projection is also a lattice, whose density divides that of \(L_t\). There are exactly \(\det(L_t(I))/\det(L_t)\) points of \(L_t\) that are projected onto each point of \(L_t(I)\). In group theory language, \(L_t(I)\) corresponds to a coset of \(L_t\).
A shifted lattice is a lattice \(L_t\) shifted by a constant vector \(\mathbf{v}_0\not\in L_t\), i.e., a point set of the form \(L'_t = \{\mathbf{v}+\mathbf{v}_0 : \mathbf{v} \in L_t\}\), where \(L_t\) is a lattice. The uniformity of a shifted lattices \(L'_t\) can be analyzed by subtracting the shift and analyzing the (unshifted) lattice \(L_t\).
There are a few algorithms specifically doing lattice manipulations implemented in LatticeTester. The first is the computation of a diagonal basis for a lattice. Given a lattice basis \(\mathbf{V}\), there always exist a unimodular matrix \(T\) such that
\begin{equation} T\mathbf{V} = \begin{bmatrix} \hat{v}_{11} & \hat{v}_{12} & \cdots & \hat{v}_{1t} \\ 0 & \hat{v}_{22} & \cdots & \hat{v}_{2t} \\ \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & \hat{v}_{tt} \end{bmatrix}. \end{equation}
Since \(T\) is unimodular, \(T\mathbf{V}\) is still a basis for the lattice \(\Lambda_t\) and can be used in place of \(\mathbf{V}\) to perform computations. Lets note the lines of \(\mathbf{V}\) as V[i] and define the following algorithm:
Then the next algorithm transforms V in a diagonal basis for lattice \(\Lambda_t\):
Having the preceding algorithm is usefull to compute the m-dual of a lattice. When m is known, it is easy to extrapolate the m-dual from a diagonal basis because the matrix \(m\mathbf{W}\) such that \(\mathbf{V}(m\mathbf{W})^t = m\mathbf{I}\) is a basis to the m-dual. As pointed out in [5], when we know that m is right, every of the divisions in the following algorithm will be integer and the m-dual is easily choosen:
The euclidian length \(l\) of the shortest non-zero vector in the lattice \(\Lambda_t\) corresponds to the distance between the nearest lattice points. For a given lattice density, having a shorter \(l\) means that the points in the lattice are more tightly packed together on fewer parallel hyperplans, which is undesirable. As counter-intuitive as it seems, it turns out that the uniformity of the points of the lattice is maximized when the length of the shortest vector is maximized. This motivates taking this \(\ell\) as a measure of uniformity, which we want to maximize.
To make a measure of uniformity, we need to rescale the value of \(\ell\) so that it can be compared between different lattices with different densities. To do this, we need to make a parallel between lattices and sphere packings. It is possible to see a lattice as a packing of non-interlapping spheres of radius \(\ell/2\) centered on every lattice point. [4] provides the theoretical foundation needed to study this packing. It turns out that the proportion of space covered by these spheres is a good indicator of the uniformity of the points: a more even point distribution and a longer \(\ell\) mean that points are at a more even distance, which is preferable if we want an even point distribution.
Using what is available in [4], it is also possible to provide bounds on the length \(\ell\). Let \(V_t\) be the volume of a sphere in dimension \(t\). Then the proportion of space taken by spheres of radius \(\ell/2\) centered on each point of the lattice is
\[\Delta_t = \frac{V_t \ell n}{2^t}.\]
With this equation it is to rewrite
\[\ell = 2 \left(\frac{\Delta_t}{V_t n}\right)^{1/t} \leq 2\left(\frac{\Delta_t^*}{V_t n}\right)^{1/t}.\]
where \(\Delta_t^*\) is a bound on \(\Delta_t\). [4] provides various values for Hermit constants ([4], [19]) \(\gamma_t = 4(\Delta_t^*/V_t)^{2/t}\) that LatticeTester uses in subclasses of the Normalizer class to give a bound on \(\ell\) as \(\ell \leq \gamma_t^{1/2} \det(L_t)^{1/t}\).
Using these bounds, it is possible to build figures of merit. Figures of merit are values scaled between 0 and 1 that can be used to easily compare different lattice with different \(n\) with some criterion specified beforehand. LatticeTester does not, however, provide figures of merit by itself so this topic is not covered more in depth here.
The work previously done with \(\Lambda_t\) can also be applied on the shortest non-zero vector of \(\Lambda_t^*\) the m-dual of \(\Lambda_t\). The normalization \(\ell(\Lambda_t^*)/\ell^*\), with the upper bound \(\ell^*\), is called the spectral test and it is a widely used computation to assess the uniformity of a lattice. Geometrically, \(1/\ell(\Lambda_t)\) is the distance between the familly of hyperplans the furter away from each other that cover the points of the lattice. A large value of \(1/\ell(\Lambda_t^*)\) means large empty portions of space without points, this is undesirable when building a uniform lattice. The Spectral Test is a widely used figure of merit on lattices (see [12], [13], [15]), especially when researching random number generators.
Finding the shortest non-zero vector is equivalent to the resolution of the following quadratic integer programming problem:
\begin{align} \text{Minimize } & & \Vert \mathbf{v} \Vert^2 & = \mathbf{v}^\mathbf{t} \mathbf{v} & & \\ \\ \text{Subject to } & & \mathbf{v} & = \sum_{i=1}^t z_i \mathbf{v}_i \\ & & 0 & < \sum_{i=1}^t |z_i|\\ & & & z_i \in \mathbb{Z}. \end{align}
Solving this problem requires the usage of integer programming and of an algorithm that will ultimately amount to enumerating all the points. There exists a Branch-and-Bound (B&B) procedure that specifically targets this problem first introduced in [6], than improved with [7] and presented in [12]. It is implemented in LatticeTester. Just like every B&B algorithm, this algorithm can take up to exponential time in \(t\). To speed up its computation, LatticeTester also provides other reduction algorithms that can be applied beforehand, so that search on the basis can be applied on already short vectors with a much smaller search space.
We first present the 3 reduction algorithms available in LatticeTester before exposing in detail the B&B procedure.
Pairwise reduction (sometimes called Dieter reduction) is a long known heuristic based on the Gram-Schmidt orthogonalization. It was first used on this exact problem by Dieter in [6].
Let first recall and introduce our notation for the Gram-Schmidt orthogonalization. From the basis \(\{\mathbf{v}_1, \ldots, \mathbf{v}_t\}\), we can get an orthogonal basis \(\{\hat{\mathbf{v}}_1, \ldots, \hat{\mathbf{v}}_t\}\) by taking
\begin{align*} \hat{\mathbf{v}}_1 & = \mathbf{v}_1 \\ \hat{\mathbf{v}}_i & = \mathbf{v}_i - \sum_{j=1}^{i-1} \mu_{ij} \hat{\mathbf{v}}_j,\ 1< i \leq t\\ \mu_{ij} & = \frac{\mathbf{v}_i \cdot \hat{\mathbf{v}}_j}{\hat{\mathbf{v}}_j \cdot \hat{\mathbf{v}}_j},\ 1 \leq j < t,\ i > j \end{align*}
The heuristic consists in trying to reduce the length of a basis vector \(\mathbf{v}_i\) by subtracting from it \(q\) times another basis vector \(\mathbf{v}_j\), for some integer \(q\) and given indices \(i\not=j\). We want to choose \(q\) as a local minima for \(\Vert \mathbf{v}_i - q \mathbf{v}_j\Vert\). This means that we want
\begin{equation} \Vert \mathbf{v}_i - (q-1) \mathbf{v}_j \Vert^2 \geq \Vert \mathbf{v}_i - q \mathbf{v}_j \Vert^2 \leq \Vert \mathbf{v}_i - (q+1) \mathbf{v}_j\Vert^2 \\ \mathbf{v}_j \cdot \mathbf{v}_j + 2(\mathbf{v}_i - q \mathbf{v}_j) \cdot \mathbf{v}_j \geq 0 \leq \mathbf{v}_j \cdot \mathbf{v}_j - 2(\mathbf{v}_i - q \mathbf{v}_j) \cdot \mathbf{v}_j \\ -\mathbf{v}_j \cdot \mathbf{v}_j \leq 2(\mathbf{v}_i - q \mathbf{v}_j) \cdot \mathbf{v}_j \leq \mathbf{v}_j \cdot \mathbf{v}_j \\ -\frac{1}{2} + \frac{\mathbf{v}_i \cdot \mathbf{v}_j}{\mathbf{v}_j\cdot\mathbf{v}_j} \leq q \leq \frac{1}{2} + \frac{\mathbf{v}_i \cdot \mathbf{v}_j}{\mathbf{v}_j\cdot\mathbf{v}_j} \end{equation}
The last line means that \(q = \lfloor1/2 + \frac{\mathbf{v}_i \cdot \mathbf{v}_j}{\mathbf{v}_j\cdot \mathbf{v}_j}\rfloor\) is a suitable integer solution to the problem. By taking this \(q\) we also get that \(\Vert \mathbf{v}_i - q \mathbf{v}_j \Vert <= \Vert \mathbf{v}_i \Vert\).
Pairwise reduction can then be written as the following algorithm with V[i], \(t\)-dimensional vectors that are the rows of a matrix:
Since the algorithm is garanteed to reduce the vector length whenever it modifies a vector, it is also garanteed to stop at one point because there is minimal attainable length.
As noted by Dieter, pairwise reductions can also be applied conjointly on the primal and dual basis. The idea is simply to make it so that every time a vector is modified, the other basis is changed accordingly so that \(\mathbf{V}\mathbf{W} = mI\) at all times. More details are available in [6].
Lenstra, Lenstra, and Lovasz [17] have proposed a popular form of lattice basis reduction known as LLL reduction. Our software implements or uses (via a library implementation) a slightly modified version of this algorithm presented in [22].
For \(1/4 \leq \delta < 1\) (usually close to 1), we say that a basis is \(\delta\)-LLL reduced if
As stated by Victor Shoup in the NTL documentation, The conditions that the vectors respect when reduced with the LLL algorithm do not have a clear geometric meaning, but a \(\delta\)-LLL reduced basis with its vectors \(\{\mathbf{v}_1, \ldots, \mathbf{v}_t\}\) ordered by length satisfies the following:
\[ (\delta-1/4)^{i-1} \leq \Vert\mathbf{v}_i\Vert^2 \lambda_i^{-2} \leq (\delta-1/4)^{1-t},\ 1 \leq i \leq t \]
with \(\lambda_i\) the \(i\)-th shortest non-zero vector in the lattice. This condition gives a relatively tight bound on the shortest vector in the basis after the \(\delta\)-LLL reduction. This vector is often much shorter than the one obtained with pairwise reduction and yields a faster B&B. It is also notable that, in large dimensions for which the B&B is impractical, this short vector can be used as an approximation of the shortest non-zero vector in the lattice.
Schnorr and Euchner give the following algorithm for \(\delta\)-LLL reduction that is used in LatticeTester on a lattice basis in matrix V, 1/2 < delta < 1 and prec the number of bits in the floating point arithmetic:
This algorithm performs in polynomial time and usually does not suffer from precision problems that may arise from the usage of floating point numbers.
The final reduction algorithm available in LatticeTester is the Block Korkine-Zolotarev (BKZ) reduction. The objective of this reduction algorithm is to provide a generalization of the previous LLL algorithm that gives stronger bounds on the results. As it is, the LLL algorithm only considers a condition on basis vectors two at a time. BKZ however generalizes LLL by changing the condition 2 to:
\[ \delta \Vert \hat{\mathbf{v}}_i \Vert^2 \leq \lambda_1(L^i(\mathbf{v}_1, \ldots, \mathbf{v}_{\min(i+\beta-1, t)}))^2,\ 1 \leq i \leq t-1. \]
where \(2 \leq \beta < t\) is called a block size, \(\lambda_1(L)\) is the shortest vector in lattice \(L\) and \(L_i(b_1, \ldots, b_n)\) is the projection of \(\{b_1,\ldots, b_n\}\) on \(\{\mathbf{v}_1, \ldots, \mathbf{v}_{i-1}\}\), which is a lattice of rank \(t-i+1\). A lattice respecting this condition and the condition 1 of \(\delta\)-LLL reduction is called \(\delta\)-BKZ with block size \(\beta\).
BKZ reduction has been introduced in [23] and perfected to use a variable precision in [22]. It turns out that BKZ reduction gives tighter bounds on the shortest obtained vector in the reduced basis: provided that \(\beta-1\) divides \(t-1\) theorem 2.3 in [23] gives
\[ \lambda_1(L_t)^2 \leq \Vert \mathbf{v}_1 \Vert^2 \leq \alpha_\beta^{(t-1)/(\beta-1)} \lambda_1(L_t)^2 \]
as a bound on the first vector in the basis. Note that \(\alpha_\beta\) is a constant with \(\alpha_2 = \frac{4}{3}\) and generally \(\alpha_\beta \leq \beta^{1+\ln\beta}\). This implies that \(1 < \alpha_\beta^{1/(\beta-1)} \rightarrow 1\) as \(\beta\) increases. This is better than what can be achieved with LLL, which is
\[ \lambda_1(L_t)^2 \leq \Vert \mathbf{v}_1 \Vert^2 \leq \frac{4}{3}^{t-1} \lambda_1(L_t)^2. \]
Note that, in reality, these bounds differ a little from this theory since the implemented algorithms use the floating point versions \(\delta\)-LLL and \(\delta\)-BKZ for efficiency.
LatticeTester does not provide an implementation for the BKZ reduction algorithm and relies on the NTL library to perform it. We therefore do not provide pseudo-code of this algorithm.
The previous sections could have been confusing because there are many variants to the presented algorithms. This is because the two algorithms cannot generally be performed in polynomial time, but weakening their conditions with the \(\delta\) factor gives way better bounds on execution times. LatticeTester implements and uses these weakened versions. Some theory that does not concern those versions is presented for comparison purposes only.
We now address the problem of computing a shortest nonzero vector with length \(\ell\) in the lattice \(\Lambda_t\). This problem amounts to finding integers \(z_1,\dots,z_t\), not all zero, such that the vector \(\mathbf{v} = z_1 \mathbf{v}_1 + \cdots + z_t \mathbf{v}_t\) is as short as possible. Trying all combinations for those \(z_j\)'s is definitely not an efficient option. For the Euclidean norm, we formulate this problem as a quadratic integer programming (optimization) problem with decision variables \(z_1,\dots, z_t\), and show how to solve it by a branch-and-bound (BB) procedure. Following the ideas of [6] [7], we get the formulation we eluded to before:
\begin{align} \text{Minimize } & & \Vert \mathbf{v} \Vert^2 & = \mathbf{v}^\mathbf{t} \mathbf{v} & & \\ \\ \text{Subject to } & & \mathbf{v} & = \sum_{i=1}^t z_i \mathbf{v}_i \\ & & 0 & < \sum_{i=1}^t |z_i|\\ & & & z_i \in \mathbb{Z}. \end{align}
Suppose that the basis vectors \(\mathbf{v}_1,\dots,\mathbf{v}_t\) are ordered by increasing length and that our best solution so far is the vector \(\mathbf{v}_1\), with square length \(\hat{\ell} = \mathbf{v}'_1 \mathbf{v}_1\). This \(\hat{\ell}\) is an upper bound on the length \(\ell\) of a shortest vector.
In the B&B algorithm, we fix successively \(z_t\), then \(z_{t-1}\), then \(z_{t-2}\), down to fixing \(z_1\). Without any more constraints, this yields an (possibly infinite) exponentially growing tree. To avoid this, at each step, for any fixed values of \(z_t,\dots,z_{j+1}\), we compute a finite range (interval) of values of \(z_j\) such that all values outside that range cannot lead to a better solution than \(\hat{\ell}\). All These values will be tested to verify that there is no possible shorter vector than the one we currently know. When a shorter vector is found, \(\mathbf{v}_1\) is changed to that new vector and the search continues. The search ends when all combinations of \(z_j\) inside the intervals have been tested.
Computing an interval for \(z_j\) is the main challenge of this problem. We present the approach of [2] to get this interval. This is what is implemented in LatticeTester.
At the beginning of the B&B procedure, as in [1] [7] [9] [21], we compute a Cholesky decomposition [8] of the matrix of scalar products of basis vectors \(\mathbf{V}\mathbf{V}^t\) which always is positive-definite:
\[ \mathbf{V} \mathbf{V}^t = \mathbf{U}^t \mathbf{U} \]
where \(\mathbf{U}\) is an upper triangular matrix:
\[ \mathbf{U} = \begin{pmatrix} u_{11} & \ldots & u_{1t} \\\ \vdots & \ddots &\vdots \\\ \mathbf{0} & \ldots & u_{tt} \end{pmatrix} \]
Now, if \(\mathbf{z} = (z_1,\dots,z_t)\), we have a shortest vector candidate \(\mathbf{v} = \mathbf{V}^t\mathbf{z}^t\). Note \(r_j = \sum_{k=j+1}^t u_{jk} z_k\), and \(s_j = \sum_{k=j+1}^t \left(\sum_{l=k}^t u_{kl} z_l\right)^2\), then we have [1] [7] [21] :
\begin{eqnarray*} \mathbf{v}^t\mathbf{v} &=& \mathbf{z}\mathbf{V} \mathbf{V}^t \mathbf{z}^t = \mathbf{z}\mathbf{U}^t \mathbf{U} \mathbf{z}^t = \sum_{k=1}^t \left(\sum_{l=k}^t u_{kl} z_l\right)^2 \\\\ &\ge& \left( u_{jj} z_j + \sum_{l=j+1}^t u_{jl} z_l\right)^2 + \sum_{k=j+1}^t \left(\sum_{l=k}^t u_{kl} z_l\right)^2 \\\\ &=& (u_{jj} z_j + r_j)^2 + s_{j} \quad = \; s_{j-1}. \end{eqnarray*}
A better solution must satisfy \(\mathbf{v}^t\mathbf{v} < \mathbf{v}_1^t \mathbf{v}_1\), which implies \((u_{jj} z_j + r_j)^2 + s_j < \mathbf{v}_1^\mathbf{t} \mathbf{v}_1\). centering the inequalities around \(z_j\) gives the following bounds
\[ \left\lceil {-(\mathbf{v}_1^\mathbf{t} \mathbf{v}_1-s_j)^{1/2} - r_j\over u_{jj}}\right\rceil \;\le z_j\le\; \left\lfloor {(\mathbf{v}_1^\mathbf{t} \mathbf{v}_1-s_j)^{1/2} - r_j\over u_{jj}}\right\rfloor. \tag{bounds} \]
Note that to obtain these bounds, the knowledge of \(z_t,\dots,z_j\) is needed and that this strategy uses the continuous relaxation of the original problem. Finding and applying those bounds is a cutting plane method. The numbers obtained mean that the possible values of \(z_j\) to find a shorter vector in the lattice are in the interval. We can restrict ourselves to the integers that lie in that interval when branching from the node \(\{z_t,\dots, z_j\}\). Note that \(s_t = r_t = 0\), so at the beginning the bounds on \(z_t\) are given by \(z_t^2 \le \mathbf{v}_1^\mathbf{t} \mathbf{v}_1\).
The algorithm explores a B&B tree in which each node corresponds to a partial solution \((z_t,\dots,z_{j})\). This node has a child \((z_t,\dots,z_{j},z_{j-1})\) for each value of \(z_j\) that satisfies the bounds and the root has a child for each \(z_t\) such that \(z_t^2 \le \mathbf{v}_1^\mathbf{t} \mathbf{v}_1\). When no \(z_j\) satisfies the bounds (when the interval is empty) the corresponding node has no child and the branch is a dead end. When we reach a tree leaf that represents a full admissible solution \((z_t,\dots,z_1)\), we have just found a shorter vector \(\mathbf{v}\) than our current shortest vector \(\mathbf{v}_1\). We can then update the basis in a way that it contains \(\mathbf{v}\) as its new \(\mathbf{v}_1\), and change the other vectors in a way that they still form a basis of our lattice.
More specifically (without repeating the computations above) the B&B algorithm of LatticeTester is the following, using V a lattice generator matrix with vectors ordered by length, t the dimension, z a candidate for the last h values of \(z\).
To call this function, one would use the generator matrix for V, \(t\) as t, an empty vector as z and h=0. This assumes that GetBounds returns the lower and upper bounds as above and that Sort sorts the vectors in V such that ||V[i]|| < ||V[j]|| if 0 <= i < j < t.
This algorithm stops when every node in the tree returns false. This means that there is no combination of \(z_j\) that yields a shorter vector for the lattice than the current V[0] and that this V[0] therefore is the shortest non-zero vector in the lattice. Note that this can use a static computation of the Choleski decomposition that is only updated when V changes or when the function is called for the first time. This would reduce the computing time dramatically. Although this does not change the exactitude of the algorithm, surveying \(z\)'s is a different order in the while loop can shorten the execution time. We use i = (min+max)/2 first, then i = (min+max)/2±1, i = (min+max)/2±2, ... which we experimentally determined to be the fastest way to get to a solution leaf that improves the current shortest vector (note that this is not exactly what is in the pseudo-code to make it more readable). Finally, since finding a new shorter vector can consequently reduce the size of the tree by giving way better cuts, each time the length of the vector is shortened, we go back to the root of the tree.
The total time taken by this B&B algorithm is roughly proportional to the number of tree nodes visited. One major drawback is that in the worst case, this number of nodes typically grows exponentially with the dimension. It is therefore important to reduce this number as much possible. It helps to start with a basis in which \(\mathbf{v}_1\) is shorter. This shortens the search interval determined by the bounds at each level \(j\), and can greatly reduce the number of nodes that must be examined. The lattice reduction algorithms presented above (Lattice Reduction Algorithms) are part of LatticeTester to overcome this difficulty. For the same reason, it also helps it we quickly find a tree leaf that corresponds to an improved solution, because it can reduce the size of the tree.
Observe that if \(\mathbf{v} = \mathbf{z}\mathbf{V}\) is a lattice vector, \(-\mathbf{v} = (-\mathbf{z})\mathbf{V}\) is also a lattice vector with the same norm. We can exploit this symmetry to cut the BB tree in half, simply by considering only non-negative values of \(z_t\). We can do that because any vector \(\mathbf{z}\) with \(z_t < 0\) has an equivalent vector \(-\mathbf{z}\) having \(z_t > 0\).
1.8.15