Alternate Choices of $\lambda$

In Section 2.2.2 above we looked at the effect of placing restrictions on the possible values of $\lambda$ on the performance of Seysen's algorithm. In particular, $\lambda$ was allowed either to be any integer value, or to only take on the values $\pm 1$. We found that the algorithm worked slightly better if row moves were chosen with $\lambda \in {\Bbb Z}$ but only $T_{i,j}^\lambda$ moves with $\lambda = \pm 1$ were actually performed, probably because the changes made to the lattice basis on any single row move are smaller. We pay for the improved performance, however, though an increase in the running time of the overall algorithm, as it takes more row operations with the restriction in place to add a large integer multiple of one basis vector to another basis vector. As an example of other possible methods of choosing or restricting $\lambda$ values, consider the following set of restrictions:

• When choosing a pair of vectors for a row move, $\lambda$ may take on any integer value.
• When the row move is actually performed, if $\lambda >0$ use the largest power of two strictly less than $\lambda$ (unless $\lambda = 1$, in which case $\lambda$ should be used). If $\lambda <0$ use the smallest power of two strictly greater than $\lambda$ (again, unless $\lambda = -1$, in which case -1 should be used).

We may abbreviate this set of conditions as $({\Bbb Z},2^k)$. What we are doing is computing the best possible value of $\lambda$, but instead of performing one row move to compute $\bold{b_j} \leftarrow \bold{b_j} + \lambda\bold{b_i}$, we perform a logarithmic number of moves. In this way we might be able to combine the benefits of the $({\Bbb Z},{\Bbb Z})$ approach (fast running time) and the $({\Bbb Z},\pm 1)$ approach (better overall performance). This approach has not been tested, and judging from the relative differences noticed between the $({\Bbb Z},{\Bbb Z})$ and $({\Bbb Z},\pm 1)$ cases is not likely to produce very large changes in reduction performance. However, it is an example of other possible $\lambda$ restrictions which could be tried.