Empirical Analysis

In the previous section we attempted to provide some theoretical justification for Seysen's basis reduction algorithm. The basic analysis suggests that Seysen's technique is viable, but as yet there are no significant bounds on the running time of the algorithm. In this section we detail numerical experiments which were performed using Seysen's algorithm. These experiments yield greater insight into the classes of lattices best suited for reduction by Seysen's algorithm, as well as an indication of the effectiveness of Seysen's technique. Before we begin detailing the empirical results it is appropriate to detail our test conditions. All implementations of Seysen's basis reduction algorithm and the LLL algorithm were written in FORTRAN. Multiprecision floating point arithmetic operations were performed by a package of routines written by David Bailey at the NASA Ames Research Center [4]. Tests were run on Silicon Graphics, Inc., IRIS-4D workstations; the IRIS uses the MIPS R3000 chip set as its main processor. The experiments described below explore many of the same aspects of Seysen's algorithm discussed in the previous section. Section 2.2.1 compares lazy and greedy schemes for choosing the row move to perform on each iteration of the algorithm. The effects of restricting $\lambda$ choices are discussed briefly in Section 2.2.2. Sections 2.2.3 and 2.2.4 compare the performance of Seysen's algorithm with the LLL lattice on two classes of lattice bases.