Alternate S(A) Functions

Section 2.1.3 above gave reasons for using functions of the product terms $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$. In particular, the function

$$S(A) = \sum_{i=1}^n a_{i,i} a_{i,i}^* = \sum_{i=1}^n \Vert\bold{b_i}\Vert^2 \Vert\bold{b_i^*}\Vert^2$$

was selected as the Seysen measure function because it yielded a closed form solution for the optimal value of $\lambda$ given i and j. However, other functions could certainly be employed as the method of comparing different lattice bases. In this section we briefly describe how Seysen's algorithm would have to be modified to accommodate another measure function. We restrict our attention to versions of Seysen's algorithm which use only row moves involving two basis vectors (i.e. $\bold{b_j} \leftarrow \bold{b_j} + \lambda\bold{b_i}$). Recall that the formula in Equation 2.9 for the optimal choice of $\lambda$ was derived by maximizing the change in the Seysen measure function caused by a row move involving two particular basis vectors. In the Seysen measure function is changed, the only direct impact it will have upon the operation of the algorithm is that the optimal value of $\lambda$ for basis vectors $(\bold{b_i},\bold{b_j})$ will be computed in a different manner. In [38] Seysen mentions two possible replacements for the S(A) function:
$$\begin{align*}S_1(A) & = \prod_{i=1}^n a_{i,i} a_{i,i}^* = \prod_{i=1}^n \Vert\... ...i}^*} = \sum_{i=1}^n \Vert\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert. \end{align*}$$
Replacing S(A) with S₁(A) implies that our choice of $\lambda$ must minimize:
$$\begin{align*}\Delta(i,j,\lambda) & = S_1(T_{j,i}^\lambda \;A \;T_{i,j}^\lambda)... ...{j,j} {a_{j,j}^*}' - a_{i,i} a_{i,i}^* a_{j,j} a_{j,j}^* \right). \end{align*}$$
Solving $\frac{\partial \Delta}{\partial \lambda} = 0$ yields an extremely complex expression for $\lambda$. Similar results occur when we try to substitute S₂(A) for S(A). In both cases, no simple closed-form solution for $\lambda$ exists as was the case with S(A). It may be still be possible to utilize measure functions in Seysen's algorithm with no simple closed-form solution for $\lambda$ if we are willing to sacrifice some performance. If the range of possible integer $\lambda$ values is bounded, for given i and j we can compute $\Delta(i,j,\lambda)$ for all possible $\lambda$ values in the permitted range. The $\lambda$ which provides the greatest change may then be selected. The cost of this procedure is that we can no longer guarantee that the maximal $\lambda$ for a pair of basis vectors $(\bold{b_i},\bold{b_j})$ may be found in constant time. If the range of $\lambda$ values to consider is usually small, then we will probably notice little more than a linear slowdown in the running time of the algorithm. For large ranges of possible $\lambda$ values, further heuristics might be applied, such as only considering $\lambda$ values which are near a power of two. In our experiments we noticed that large $\lambda$ values tended to occur only during the first few row reduction performed by Seysen's algorithm. After this initial burst in reduction of S(A) row moves tended only to involve small integer $\lambda$ values; it was quite rare to find $\vert\lambda\vert > 10$. If similar conditions occur for the lattice bases in question, it is probably reasonable to use a more complex measure function than S(A) and use a small exhaustive search over a bounded range of possible $\lambda$ values to find the optimal $\lambda$ coefficient for a row move.