Theoretical Analysis

We consider first the theoretical foundations of Seysen's basis reduction algorithm. There are a number of questions concerning the actual structure of the algorithm which immediately arise. For a given quadratic form A, how might the S-reduced and S₂-reduced forms derived from A differ? Is it even sufficient to consider only $T_{i,j}^\lambda$ transformation matrices, or are there lattices for which it is impossible to find the S-reduced form using only $T_{i,j}^\lambda$ transformations? How do we choose the order in which to apply the $T_{i,j}^\lambda$ transformations, or equivalently how do we choose pairs of basis vectors for row moves? Is the Seysen measure function $S(A) = \sum_{i=1}^n a_{i,i} a_{i,i}^*$ a ``good'' way to rank different bases of a lattice? Finally, given that S(A) is an acceptable measure function, is our choice of $\lambda = \lceil \frac{1}{2}(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}) \rfloor$, given i and j, optimal? This section considers theoretical justifications for all of these questions. Section 2.2 below considers these questions from an empirical point of view.