Choosing Vector Pairs to Reduce

Seysen's algorithm does not specify how to choose which pair of basis vectors $(\bold{b_i},\bold{b_j})$ to reduce on each iteration of the algorithm. At every iteration, it is necessary to find an (i,j) pair for which there exists a transformation matrix $T_{i,j}^\lambda, \lambda \neq 0$, such that:

$$S(T_{j,i}^\lambda \;A \;T_{i,j}^\lambda) < S(A).$$

Therefore, given that initially there are likely to be many pairs of vectors which may be reduced, we must decide how to select the best pair. Two options appear immediately as candidate vector selection methods: lazy selection and greedy selection. A lazy selection scheme simply chooses any available (i,j) pair in the easiest possible manner. For example, we can imagine two nested loops which generate (i,j) pairs and stop at the first pair for which $\lambda(i,j) \neq 0$, where

$$\lambda(i,j) = \left\lceil \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right) \right\rfloor.$$

Once such a pair is found, a $T_{i,j}^{\lambda(i,j)}$ transformation can be performed on the lattice basis. Then the algorithm could search for another (i,j) pair, perhaps continuing the search at the first pair lexicographically after (i,j). The second possible candidate selection method is a greedy approach. Here we calculate $\Delta(i,j,\lambda)$ for each possible pair (i,j), where $\Delta(i,j,\lambda)$ is defined:

$$\Delta(i,j,\lambda) = S(T_{j,i}^\lambda \;A \;T_{i,j}^\lambda) - S(A).$$

Thus, any transformation matrix $T_{i,j}^\lambda$ will have $\Delta(i,j,\lambda) < 0$. The algorithm then uses the pair of vectors $(\bold{b_i},\bold{b_j})$ which minimizes $\Delta(i,j,\lambda)$ in the next row move. One immediate disadvantage to a greedy approach is that it requires more extensive computations than the lazy selection method. This is true of any set of selection criteria which attempts to choose vector pairs to reduce in some fashion which performs better than random selection. If the two selection methods yield reduced bases of comparable Seysen measure, the added cost of an ``intelligent'' method may be greater than the time saved by reducing the number of row operations. However, if one method should yield lattices with lower Seysen measure, the extra costs may be justified. We should point out that there is a distinction between choosing a pair of vectors to reduce and actually performing the reduction. Choosing a pair of vectors to reduce because they have the greatest potential to reduce the Seysen measure does not necessarily imply that we should perform the entire reduction and use the largest possible value of $\lambda$. It may be wise to perform only a fraction of the possible row moves and reevaluate other possible pairs of vectors. We run the risk, if we are too greedy, of getting stuck too soon in a local minimum. There are reasons both to favor and to suspect the value of intelligent vector pair selection methods. One of the advantages that Seysen's method has over the LLL family of basis reduction algorithms is that it looks at all the vector pairs simultaneously. The LLL algorithm works in a fashion similar to a bubble sort and LLL only considers row operations involving ``adjacent'' basis vectors (i.e. $\bold{b_i}$ and $\bold{b_{i-1}}$ for $2 \leq i \leq n$). The cost of intelligent selection methods in terms of additional operations is certainly a disadvantage, but only if the cost is a significant fraction of the total running time. Section 2.2.1 below discusses these issues and presents empirical evidence of the cost and performance of a number of selection schemes for Seysen's algorithm. From our experiments, the greedy selection scheme performs better than the lazy scheme, and the additional computation required to implement greedy selection is small.