Conclusions

We have shown in this thesis that Seysen's lattice basis reduction algorithm performs much better than other currently available techniques in a limited number of circumstances. In particular, we have demonstrated that Seysen's algorithm may be combined with the LLL algorithm to solve subset sum problems. As a general lattice basis reduction tool, however, Seysen's algorithm leaves much to be desired. The lack of theoretical bounds on the running time and performance of the algorithm is discouraging. Empirical tests performed using Seysen's algorithm also highlight weaknesses with using this method to solve general lattice reduction problems. As the first part of this thesis demonstrated, the performance of Seysen's algorithm on randomly generated ``dense'' lattice bases degrades quickly as the dimension of the lattice increases above a certain critical bound. There are numerous local minima of the S(A) function for these lattices, and once Seysen's algorithm encounters one it is unable to escape (without some external influence acting upon the lattice basis). Seysen's algorithm should not be immediately discounted, however. In certain specific cases the algorithm performed quite well. In general Seysen's algorithm performs only a fraction of the row moves required by the LLL algorithm to reduce a lattice basis. For certain lattices, such as the $B_{\theta }$ lattices of Section 2.2.3, the LLL algorithm was unable to perform any row reductions, whereas Seysen's algorithm enjoyed great success. Even for dense lattices, if the dimension of the lattice is relatively small, Seysen's algorithm obtains the same results as LLL in only a fraction of the time. Applications which utilize basis reduction in few dimensions are good candidates for Seysen's method. The experiments performed on lattices derived from subset sum problems highlight one of the main advantages of Seysen's technique: its ability to very quickly perform significant reductions on a lattice basis. Using Seysen's algorithm as a first reduction stage allowed us to convert lattice bases involving large, multiprecision values into other bases with vector coefficients which could be represented in single- or double-precision. The LLL algorithm could then be run without having to use multiprecision arithmetic, which greatly improved its execution time. For larger lattices (with $n \approx 100$) one must be aware of possible problems due to rounding and truncation errors, but these difficulties can be overcome. Although the primary goal of this thesis was to investigate applications of Seysen's basis reduction algorithm, one should not overlook the other techniques which were used (in addition to Seysen's algorithm) to solve subset sum problems. In particular, the theoretical improvements to the Lagarias-Odlyzko attack in [12] may be directly incorporated into practical methods of solving subset sum problems. Also, the use of multiple values of the y parameter in the LLL algorithm significantly reduced the total number of row moves LLL performed. This modification does not appear to decrease the reduction performance of LLL in any way over LLL with constant $y \approx 0.99$, although it does significantly reduce the running time of the algorithm. We would suggest using multiple, increasing values of y in the future whenever LLL-reduction is performed. We have demonstrated that Seysen's algorithm is a good basis reduction technique for certain types of lattices, outperforming the basic LLL algorithm in terms of the number of row operations required. Furthermore, we have seen how Seysen's algorithm may be combined with variants of the LLL algorithm and heuristic methods to successfully attack many subset sum problems with $n \lesssim 100$. Yet these specific instances are but a fraction of the type of lattice reduction problems which arise. It is therefore natural to consider what other types of lattice reduction problems are suitable for attack by Seysen's algorithm. We conclude this chapter, and the thesis itself, with some remarks on other Seysen-suitable lattices, and also suggestions for modifying Algorithm SL to solve subset sum problems of larger dimensions and higher densities.