When Seysen's Algorithm Fails

We have seen above that for random, dense lattices L with $\det(L) = 1$, Seysen's algorithm starts to break down for $30 \leq n \leq 35$. As n increases beyond 35, the number of local minima for the S(A) function apparently increases, and thus the chance that Seysen's algorithm will reduce lattice L to I_n decreases. As the number of local minima increases, it is increasingly likely that in the process of reducing lattice L the S(A) function (where A is the quadratic form associated with L) will encounter one of these local minima. As described above, Seysen's algorithm cannot tell whether it has reached a local or a global minimum. Thus, it stops as soon as all possible $T_{i,j}^\lambda$ transformations cause S(A) to increase. For many types of lattices, such as the sparse lattices generated by subset sum problems (see Chapter 3), Seysen's algorithm has performed sufficient work by the time it encounters a local minimum that it is acceptable for it to stop. However, for many lattice reduction problems Seysen's algorithm stops too soon. We would like the algorithm to be able to detect local minima and overcome them. If one considers the surface described by S(A) values, local minima are ``wells'' or ``depressions'' in the surface which are large enough to contain all points reachable by performing one row move on the lattice. In this section we discuss possible techniques for ``kicking'' the reduced lattice out of these wells; methods of enhancing Seysen's algorithm so that it may consider other options when it encounters a local minimum. There are many methods which could conceivably be applied to a lattice to move it out of a local minimum; we consider only some of these options. Section 2.3.1 considers an obvious possibility, which is to consider row moves involving 3 or 4 vectors at once (general n-moves are discussed in Section 2.4.1 below). In Section 2.3.2 we investigate simulated annealing and rapid quenching approaches to the problem. Finally, Section 2.3.3 discusses using Hadamard matrices to permute the entire lattice basis.