Candidate Lattices for Seysen Reduction

The number of ``classes'' of lattice bases which may be successfully reduced using only Seysen's basis reduction algorithm appears to be quite small. It was shown in Chapter 2 that Seysen's algorithm, which was designed for finding simultaneously good reductions of a lattice basis and its dual, indeed works well in such cases. Furthermore, if the goal of a lattice reduction is to minimize some cost function or measure of the lattice (and perhaps its dual), an appropriately modified version of Seysen's algorithm incorporating the cost function will likely perform much better than an LLL-type algorithm. While there are empirical reasons which suggest the use of the S(A) measure as a particular cost function, Seysen himself mentioned in [38] that other function had been used in the algorithm in place of S(A) with about the same degree of success. Replacing S(A) with another cost function may involve some difficulty. In particular, it may not be possible to solve for the coefficients $\lambda_i$ in closed form using an alternate cost function. If some range of acceptable values can be determined, then a search considering all integers in the range of interest may be feasible. Such an approach was used in experiments with the cost function
$$\begin{align*}S'(A) & = \sum_{i=1}^n \frac{1}{\sqrt{a_{i,i} a_{i,i}^*}}, \\ & = \sum_{i=1}^n \frac{1}{\Vert\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert}. \end{align*}$$
For a proposed row move $\bold{b_j} \leftarrow \bold{b_j} + \lambda\bold{b_i}$ it is possible to compute bounds on the range of possible $\lambda$ values. For sufficiently small ranges $\lambda \in [\lambda_1,\lambda_2]$ we compute the change in S'(A) after applying the row move with $\lambda$ taking on every integer value in the range. Then (assuming a greedy approach) we choose the value for $\lambda$ which maximized the decrease in S'(A). Thus, although it may not be possible to solve for the best choice for $\lambda$ for some proposed cost function, numerical methods may allow consideration of the metric anyway. The class of lattice bases which may be successfully reduced by using only Seysen's algorithm appears quite limited, assuming that we ignore differences in execution time. The randomly generated lattice bases with unit determinant from Chapter 2 exemplify this point: Seysen's algorithm began to perform poorly for $n \geq 35$, whereas the LLL algorithm continued to correctly reduce lattices to the n-dimensional cubic lattice for all tested cases. As a stand-alone technique, Seysen's algorithm may not be considered that useful; it works quite well for some lattices of low dimension, but it tends to stop early for larger-dimensioned lattice bases. To reduce these lattice bases some combination of Seysen's algorithm and other reduction methods is probably required.