Introduction

In 1985 Lagarias and Odlyzko [26] developed a general attack on knapsack cryptosystems which reduces solving subset sum problems to the problem of finding the Euclidean-norm shortest nonzero vector in a point lattice. Recent improvements to this attack [12,19] have stimulated interest in finding lattice basis reduction algorithms well-suited to the lattices associated with subset sum problems. This thesis studies a new approach to lattice basis reduction originally developed by M. Seysen [38]. Seysen's reduction algorithm was initially developed to find simultaneously good bases of a lattice and its dual lattice. However, it may also be successfully applied to solving subset sum problems, especially when combined with other known reduction methods. Using a collection of techniques, including Seysen's algorithm, we show that it is possible to solve in practice a much larger class of subset sum problems than was previously possible.

Point Lattices

Let B be a set of vectors $(\bold{b_1},\bold{b_2},\ldots{},\bold{b_n})$ in ${\Bbb R}^n$ . If these vectors are independent, then they form a basis of ${\Bbb R}^n$ and any point $\bold{x}$ in n-space may be written as a linear combination of vectors in B:

Consider the set of points $L \subset {\Bbb R}^n$ which may be written as the sum of integer multiples of the basis vectors:

We call this set L the point lattice (or just lattice) described by the basis B. Point lattices are pervasive structures in mathematics, and have been studied extensively. See [25], for example, for a survey of the field. In the area of combinatorial mathematics alone it is possible to phrase many different problems as questions about lattices. Integer programming [20], factoring polynomials with rational coefficients [27], integer relation finding [16], integer factoring [35], and diophantine approximation [36] are just a few of the areas where lattice problems arise. In some cases, such as integer programming existence problems, it is necessary to determine whether a convex body in ${\Bbb R}^n$ contains a lattice point (for some specific lattice). In other cases the items of interest are short vectors in the lattice. As we shall see below, for certain cryptographic applications, we would like to be able to quickly determine the Euclidean-norm shortest nonzero vector in a lattice. It is important to note that the difficulty of finding the Euclidean-norm shortest nonzero vector in a lattice is an open question. If $\bold{x} = (x_1,\ldots{},x_n)$ , then the sup-norm of $\bold{x}$ , denoted $\Vert\bold{x}\Vert _\infty$ , is defined as

It is known that finding the sup-norm shortest nonzero vector in a lattice is NP-hard [5]. Based on this evidence, we suspect that finding the Euclidean-norm shortest nonzero vector for any given lattice is also computationally difficult. However, it may be possible to find the shortest nonzero vector for many lattices quickly. Indeed, current techniques for finding short vectors are slow in theory but often perform well in practice. The remainder of this chapter establishes the environment for our study of lattices and specific applications to cryptography. Section 1.2 discusses reduced bases of lattices and lattice reduction theory. Section 1.3 mentions some of the algorithms which currently exist for computing a reduced lattice basis B' given a basis B of a particular point lattice. In particular, we detail the operation of the Lenstra-Lenstra-Lovász (LLL) basis reduction algorithm [27], which is currently the best known method for finding short vectors in a lattice.

Reduced Lattice Bases

Any lattice L may be described by many different lattice bases. Let $B_1,B_2,\ldots{}$ be distinct sets of vectors, all of which form bases of lattice L. We can imagine that there exists some ordering or ranking of the bases B_i, and thus one or more of the B_i might be considered ``good'' lattice bases of L. Lattice reduction theory deals with identifying ``good'' lattice bases for a particular lattice. If we are given a basis B which describes L, we would like to reduce B to basis B', also describing L, where B' is a ``good'' lattice basis in the sense of some reduction theory. There are two classical lattice reduction theories, one due to Korkin and Zolotarev [23,24] and one due to Minkowski [29]. A basis $B = (\bold{b_1},\bold{b_2},\ldots{},\bold{b_n})$ of lattice L is said to be Minkowski-reduced if

Minkowski-reduced lattice bases always contain the shortest nonzero vector in the lattice. Subsequent basis vectors $\bold{b_i}$ are selected by choosing the shortest lattice vector in L which is not a linear combination of the already selected basis vectors $\bold{b_1},\ldots{},\bold{b_{i-1}}$ . If $\bold{b_i} = \sum_{j=1}^{i-1} z_j \bold{b_j}, z_j \in {\Bbb Z}$ , then it would be impossible to extend ( $\bold{b_1},\ldots{},\bold{b_i}$ ) to be a basis of L. The definition of Korkin-Zolotarev reduction is similar to that of Minkowski. We say a basis $B=(\bold{b_1},\ldots{},\bold{b_n})$ is Korkin-Zolotarev reduced if it satisfies the following three conditions:

In the definition of Minkowski reduction, successive basis vectors $\bold{b_i}$ are added to the lattice basis only if $\bold{b_i}$ is the shortest vector in the lattice which will allow the basis to be extended. In Korkin-Zolotarev reduction, though, successive basis vectors $\bold{b_i}$ are chosen based on their length in the orthogonal complement of the space spanned by the previous basis vectors $\bold{b_1},\ldots{},\bold{b_{i-1}}$ . Depending on the specific problem, we may find either, both, or neither of the above definitions of ``good'' lattice bases is sufficient. Certainly if the goal is to find the shortest nonzero vector in the lattice, as is the case with subset sum problems (see Chapter 3), we could use either Minkowski reduction or Korkin-Zolotarev reduction as a measure of how ``good'' a particular lattice basis is. If the item of interest involves multiple vectors in the lattice, one definition may be preferred over the other for that particular application.

Lattice Basis Reduction Algorithms

Although both Minkowski reduction and Korkin-Zolotarev reduction provide frameworks for studying lattice basis reduction, computing a reduced lattice basis (in either sense) is in general a difficult problem. Currently, there are no known polynomial-time algorithms for finding either a Minkowski or a Korkin-Zolotarev reduced basis for a given lattice L. If such an algorithm existed, then we would be able to find the Euclidean-norm shortest nonzero vector in L in polynomial time by finding the reduced basis, for which $\bold{b_1}$ is the desired vector. Thus, any polynomial-time lattice basis reduction algorithm we use will not be able to satisfy the strict conditions of Minkowski or Korkin-Zolotarev reduction. Techniques for finding relatively small vectors in a lattice have been known for some time (see [22] for example); it was not until recently, though, that a fast algorithm was known which was guaranteed to produce lattice bases with relatively short vectors. In [27] Lenstra, Lenstra and Lovász described a polynomial-time algorithm for transforming a give lattice basis $B=(\bold{b_1},\ldots{},\bold{b_n})$ of lattice L into an LLL-reduced lattice basis $B' = (\bold{b_1'},\ldots{},\bold{b_n'})$ . A basis B' is LLL-reduced if it has the following two properties:

where the parameter $y \in (\tfrac{1}{4},1)$ and $\bold{b_j^*} = \bold{b_j'} - \sum_{i=1}^{j-1} \mu_{i,j}\bold{b_i^*}$ (That is, $B^*=(\bold{b_1^*},\ldots{},\bold{b_n^*})$ is a Gram-Schmidt orthogonalized basis generated from B). Notice that LLL reduction is similar to but weaker than Korkin-Zolotarev reduction. The Lenstra-Lenstra-Lovász basis reduction algorithm converts lattice basis B into B' by performing two types of transformations. In a size-reduction step, LLL finds the largest j such that there exists an i > j and $\mu_{i,j}$ violates Equation 1.1. By performing the transformation

where $\lceil \cdot \rfloor$ denotes the nearest-integer function, we find that the new value of $\mu_{i,j}$ is $\leq \tfrac{1}{2}$ . In the exchange step, LLL searches for the smallest value of i such that $\bold{b_{i-1}}$ and $\bold{b_i}$ fail to satisfy Equation 1.2. Here LLL swaps the two vectors ( $\bold{b_{i-1}} \longleftarrow \bold{b_i}$ and $\bold{b_i} \longleftarrow \bold{b_{i-1}}$ ) to force compliance with the second LLL-reduced condition. The LLL basis reduction algorithm alternately performs size-reduction and exchange steps until both Equations 1.1 and 1.2 are satisfied, at which point the algorithm halts. LLL-reduced lattice bases satisfy a number of bounds. In particular, if y is the global LLL constant, then the first vector in the reduced lattice basis $\bold{b_1}$ satisfies:

Thus the length of $\bold{b_1}$ is at most an exponential multiple of the length of the shortest nonzero vector in the lattice. (Similar bounds exist for the other vectors in the reduced basis.) In practice, the LLL algorithm usually performs much better than this exponential bound, although example lattice bases are known which cause the LLL algorithm to exhibit worst-case performance. Most of the work on lattice basis reduction algorithms since the introduction of LLL has focused on improving and extending the technique. For example, the version of LLL described above requires rational arithmetic (the $\mu_{i,j}$ variables in particular must be stored as fractions); multiprecision floating-point numbers are usually used to reduce the computation requirements, but may introduce error into the calculations. One method of reducing the multiprecision requirements is described in [33]. Similarly, [32] showed how to modify the LLL algorithm so that the set of input vectors can be linearly dependent. Hierarchies of LLL-type algorithms have been investigated [34], stretching from LLL-reduction at one end of the spectrum to Korkin-Zolotarev reduction at the other. However, little effort has been expended on looking at algorithms not derived from or similar to LLL. This thesis examines an approach to lattice basis reduction of different structure than that of the LLL algorithm and related methods. This method was originally suggested by M. Seysen [38] to simultaneously produce a reduced basis and a reduced dual basis for some lattice L. Where the LLL algorithm concentrates on local optimizations to produce a reduced lattice, the Seysen approach considers the entire basis for methods of optimization. (Recall that the LLL size-reduction steps only consider $\mu_{i,j}$ for the smallest possible j, and that only adjacent vectors $\bold{b_{i-1}}$ and $\bold{b_i}$ may be exchanged.) Chapter 2 describes the first phase of the research, in which Seysen's basis reduction algorithm and multiple variants were implemented and examined. Theoretical and empirical analyses of the fixed components of Seysen's algorithm are given. For those parts of the algorithm which are permitted to vary, we examine some of the possible variations, and look at the effect of these changes on the performance of the algorithm. Possible extensions of the algorithm are also discussed. The motivation behind our study of Seysen's lattice basis reduction algorithm is presented in Chapter 3. It is known that certain subset sum problems may be solved by finding the shortest nonzero vector in a particular lattice (the lattice is generated based on the specific construction of the subset sum problem). The best methods previously known for reducing subset sum problem lattices [26,33] involve the LLL algorithm and some other heuristics, and are not very successful for n > 25 (n is the size of the subset sum problem to be solved). Chapter 3 details experiments which used Seysen's algorithm in combination with the LLL algorithm and other heuristics to solve a much greater range of subset sum problems.

The Seysen Basis Reduction Algorithm

In 1988, Martin Seysen proposed a new method for performing lattice basis reduction [38]. Seysen's basis reduction algorithm (or just Seysen's algorithm) differs from the LLL algorithm and its variants in that it considers all vectors in the lattice simultaneously, and performs operations on those vectors which will reduce the lattice according to some measure. Recall that the LLL algorithm works locally on the lattice it is reducing; LLL will only perform an operation on two vectors which are adjacent to each other in the ordered lattice basis. Seysen was motivated to create a new method for basis reduction by a desire to find a better way to simultaneously reduce a lattice and its reciprocal (or dual) lattice. If lattice L is defined by basis vectors $\bold{b_1},\ldots{},\bold{b_n}$ , then the dual lattice L^* of L is defined by basis vectors $\bold{b_1^*},\ldots{},\bold{b_n^*}$ , where

Now consider what happens in the dual lattice when we perform a row move on $\bold{b_i}$ and $\bold{b_j}$ in L. (A row move is any operation which adds a constant multiple of one lattice basis vector to another basis vector.) Let $\bold{b_j'} = \bold{b_j} + \lambda\bold{b_i}$ , where $\lambda \in {\Bbb Z}$ . We consider what changes must occur in the dual lattice basis vectors $\bold{b_1^*},\ldots{},\bold{b_n^*}$ , since Equation 2.1 must hold at all times. For $k \neq i$ , we find that:
$\begin{align*}\bold{{b_k^*}'} & = \bold{b_k^*}, \\ \intertext{since} (\bold{b... ...b_j},\bold{b_k^*}) + \lambda(\bold{b_i},\bold{b_k^*}), \\ & = 0. \end{align*}$
For k = i, however, this is not the case:
$\begin{align*}\bold{{b_i^*}'} & = \bold{b_i^*} - \lambda\bold{b_j^*}, \\ \inte... ..._i},\bold{b_j^*}), \\ & = 0 - \lambda + \lambda - 0, \\ & = 0. \end{align*}$
Thus, when we add $\lambda\bold{b_i}$ to $\bold{b_j}$ in the basis of lattice L, we must subtract $\lambda\bold{b_j^*}$ from $\bold{b_i^*}$ in the basis of L^*. It is easy to see that if lattice L is reduced with the LLL algorithm, the resulting reduced lattice may have a dual in which some basis vector is quite large, as no attempt is ever made to consider the size of the dual basis when row moves are being performed. Seysen's algorithm attempts to choose row moves that reduce both the lattice and its dual. We now outline the basic operation of Seysen's algorithm. Let L and L^* be a lattice and its dual which we wish to simultaneously reduce. Let A and A^* be the associated quadratic forms of L and L^*, respectively:
$\begin{alignat*}{4} A & = & & \left[ a_{i,j} \right]_{1 \leq i,j \leq n} & & = ... ... \left[ (\bold{b_i^*},\bold{b_j^*}) \right]_{1 \leq i,j \leq n}. \end{alignat*}$
The element a_i,j of matrix A is the inner product of the basis vectors $\bold{b_i}$ and $\bold{b_j}$ of lattice L. Notice that A and A^* are inverses of each other and are symmetric. If L is the lattice defined by basis B, then any other basis B' of L may be written as:

where $T \in SL_n({\Bbb Z})$ (i.e. T is an $n \times n$ integer matrix with determinant 1). The quadratic form A' associated with B' may similarly be derived from A:

We suspect that it is computationally difficult to find the optimal transformation matrix T for a given basis B. Consider, however, the class of transformation matrices $T_{i,j}^\lambda$ defined by:
$\begin{align*}T_{i,j}^\lambda & = I_n + \lambda U_{i,j}, \quad\text{where $i \ne... ... \\ 0 & \text{if $k \neq i$\space or $l \neq j$ }. \end{cases} \end{align*}$
(The matrix U_i,j has exactly one nonzero entry. Matrix $T_{i,j}^\lambda$ has diagonal entries of 1 and exactly one nonzero off-diagonal entry.) Right-multiplying B by any $T_{i,j}^\lambda$ simply adds $\lambda$ times the $i^{\rm th}$ column of B to the $j^{\rm th}$ column of B. If the columns of B are the basis vectors $\bold{b_i}$ , then $B \;T_{i,j}^\lambda$ is simply the transformed basis $B' = (\bold{b_1},\bold{b_2},\ldots{},\bold{b_{j-1}},\bold{b_j}+\lambda \bold{b_i},\ldots{},\bold{b_n})$ . Since it is easy to perform calculations with $T_{i,j}^\lambda$ transformations, we focus our attention on products of one or more $T_{i,j}^\lambda$ transformation matrices. It can be shown that every $T \in SL_n({\Bbb Z})$ may be written as such a product:

while (A is not S₂-reduced) do choosei,j such that $\exists\ \lambda \in {\Bbb Z}$ with

where $\lceil \cdot \rfloor$ denotes the nearest-integer function. This procedure for S₂-reducing a quadratic form is Seysen's basis reduction algorithm. To date, little has been proven concerning the performance of Seysen's algorithm. There are no known bounds on the Seysen measure of an S₂-reduced basis (although bounds have been proven for S-reduced lattice bases), nor on the length of the shortest nonzero vector in the basis. The running time of Seysen's algorithm is clearly bounded if the lattice basis consists of only integer vectors, but it is not known if the algorithm even terminates for basis vectors with real coefficients. However, preliminary experiments performed by Seysen on lattices of dimension $n \leq 30$ suggest that this technique may be faster than the LLL algorithm and yield bases with shorter vectors. Based on these observations, a comprehensive investigation of theoretical and practical aspects of Seysen's algorithm was undertaken. This chapter details the results of our study of Seysen's basis reduction algorithm. Section 2.1 below discusses the theoretical underpinnings of Seysen's algorithm. Empirical tests performed with various versions of the Seysen algorithm are detailed in Section 2.2. Section 2.3 mentions some modifications which may be made to Seysen's algorithm when the performance of the basic version breaks down. Finally, Section 2.4 discusses possible extensions to Seysen's algorithm.

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.

Sufficiency of $T_{i,j}^\lambda$ Matrices

As defined above, a basis B is S-reduced if and only if its associated quadratic form A satisfies:

Thus, in order to Seysen-reduce a given lattice L which we know has basis B, we need to find a transformation matrix $T \in SL_n({\Bbb Z})$ such that for all other $T' \in SL_n({\Bbb Z})$ we have $S(T^t \;A \;T) \leq S((T')^t \;A \;T')$ . As $SL_n({\Bbb Z})$ is the set of all $n \times n$ matrices of unit determinant, we suspect that it is computationally difficult to find the desired matrix T directly. However, there are ways to avoid having to compute matrix T directly. Specifically, we can restrict our attention to a set of generating matrices for $SL_n({\Bbb Z})$ , as we show below. Initially, let us assume that n = 2 and that A is the quadratic form associated with a lattice basis we wish to reduce. $SL_2({\Bbb Z})$ thus contains all $2 \times 2$ matrices $\left[ \begin{smallmatrix}a & b \\ c & d\\ \end{smallmatrix} \right]$ with ad - bc = 1. Now, it is known [2,37] that the set G₂ is a set of generating matrices for $SL_2({\Bbb Z})$ , where:

That is, if $T \in G_2$ , then there exists a sequence of matrices $T_1,T_2,\ldots{},T_k$ such that

(Actually, the set $\left\{ \left[ \begin{smallmatrix}1 & \lambda \\ 0 & 1 \end{smallmatrix} \righ... ...\\ \lambda & 1 \end{smallmatrix}\right] \colon \lambda \in \{-1,0,1\} \right\}$ is sufficient, since
$\begin{align*}\begin{bmatrix}1 & \pm 1 \\ 0 & 1 \end{bmatrix}^\lambda & = \begi... ...lambda & = \begin{bmatrix}1 & 0 \\ \pm \lambda & 1 \end{bmatrix}. \end{align*}$
Section 2.2.2 below discusses the performance of Seysen's algorithm when we restrict $\lambda = \pm 1$ .) Notice that the matrices $\left[ \begin{smallmatrix}1 & \lambda \\ 0 & 1\\ \end{smallmatrix} \right]$ and $\left[ \begin{smallmatrix}1 & 0 \\ \lambda & 1\\ \end{smallmatrix} \right]$ describe all possible row moves which can be performed on a $2 \times 2$ matrix. As an example, note that the matrix $S_0 = \left[ \begin{smallmatrix}0 & 1 \\ -1 & 0\\ \end{smallmatrix} \right]$ is generated by:

(S₀ corresponds to swapping the two rows in a matrix.) Thus, the set of matrices $T_{i,j}^\lambda$ for $n = 2, i \neq j$ is exactly a set of generating matrices for $SL_2({\Bbb Z})$ . Therefore, it is sufficient for n = 2 for Seysen's algorithm to consider only products of matrices of the form $T_{i,j}^\lambda$ . The difficulty is in choosing the right matrices and the right order of operations. Our analysis above assumed n = 2, but similar results are known where n is an arbitrary integer [30]. For fixed n > 0,

is a set of generating matrices for $SL_n({\Bbb Z})$ . Thus, it would be sufficient for Seysen's algorithm to consider only T_i,j¹ and T_i,j^-1 transformation matrices if it could pick the proper triples $(i,j,\pm 1)$ at every step. In practice, Seysen's algorithm chooses triples $(i,j,\lambda)$ where $\lambda \in {\Bbb Z}$ , but the basic problem is still choosing the right triples in the right order. Choosing the correct (i,j) pairs to reduce and the value of $\lambda$ for that pair are discussed below.

Choosing Vector Pairs to Reduce

Seysen's algorithm does not specify how to choose which pair of basis vectors $(\bold{b_i},\bold{b_j})$ to reduce on each iteration of the algorithm. At every iteration, it is necessary to find an (i,j) pair for which there exists a transformation matrix $T_{i,j}^\lambda, \lambda \neq 0$ , such that:

Therefore, given that initially there are likely to be many pairs of vectors which may be reduced, we must decide how to select the best pair. Two options appear immediately as candidate vector selection methods: lazy selection and greedy selection. A lazy selection scheme simply chooses any available (i,j) pair in the easiest possible manner. For example, we can imagine two nested loops which generate (i,j) pairs and stop at the first pair for which $\lambda(i,j) \neq 0$ , where

Once such a pair is found, a $T_{i,j}^{\lambda(i,j)}$ transformation can be performed on the lattice basis. Then the algorithm could search for another (i,j) pair, perhaps continuing the search at the first pair lexicographically after (i,j). The second possible candidate selection method is a greedy approach. Here we calculate $\Delta(i,j,\lambda)$ for each possible pair (i,j), where $\Delta(i,j,\lambda)$ is defined:

Thus, any transformation matrix $T_{i,j}^\lambda$ will have $\Delta(i,j,\lambda) < 0$ . The algorithm then uses the pair of vectors $(\bold{b_i},\bold{b_j})$ which minimizes $\Delta(i,j,\lambda)$ in the next row move. One immediate disadvantage to a greedy approach is that it requires more extensive computations than the lazy selection method. This is true of any set of selection criteria which attempts to choose vector pairs to reduce in some fashion which performs better than random selection. If the two selection methods yield reduced bases of comparable Seysen measure, the added cost of an ``intelligent'' method may be greater than the time saved by reducing the number of row operations. However, if one method should yield lattices with lower Seysen measure, the extra costs may be justified. We should point out that there is a distinction between choosing a pair of vectors to reduce and actually performing the reduction. Choosing a pair of vectors to reduce because they have the greatest potential to reduce the Seysen measure does not necessarily imply that we should perform the entire reduction and use the largest possible value of $\lambda$ . It may be wise to perform only a fraction of the possible row moves and reevaluate other possible pairs of vectors. We run the risk, if we are too greedy, of getting stuck too soon in a local minimum. There are reasons both to favor and to suspect the value of intelligent vector pair selection methods. One of the advantages that Seysen's method has over the LLL family of basis reduction algorithms is that it looks at all the vector pairs simultaneously. The LLL algorithm works in a fashion similar to a bubble sort and LLL only considers row operations involving ``adjacent'' basis vectors (i.e. $\bold{b_i}$ and $\bold{b_{i-1}}$ for $2 \leq i \leq n$ ). The cost of intelligent selection methods in terms of additional operations is certainly a disadvantage, but only if the cost is a significant fraction of the total running time. Section 2.2.1 below discusses these issues and presents empirical evidence of the cost and performance of a number of selection schemes for Seysen's algorithm. From our experiments, the greedy selection scheme performs better than the lazy scheme, and the additional computation required to implement greedy selection is small.

The S(A) Function

Equation 2.2 above introduced the Seysen measure function $S(A) = \sum_{i=1}^n \Vert\bold{b_i}\Vert^2 \Vert\bold{b_i^*}\Vert^2$ ; the entire operation of Seysen's lattice basis reduction algorithm centers on this quantization of relative reduction of two bases of lattice L. It is natural to question whether Seysen measures are indeed a reasonable means of ranking different lattice bases. We mention here some of the theoretical evidence which suggests that ranking lattice bases by their Seysen measure is appropriate. The use of the quantity $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ derives from elementary n-dimensional geometry. Recall the definition of the dual lattice $B^*=(\bold{b_1^*},\ldots{},\bold{b_n^*})$ of lattice B:

where $\delta_{i,j}$ is the Dirac delta function ( $\delta_{i,j} = 1$ if i = j, $\delta_{i,j} = 0$ otherwise). Now, fix i and notice that
$\begin{align}\left( \bold{b_i}, \bold{b_i^*} \right) & = 1, \notag \\ \Vert\bo... ...\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert & = \frac{1}{\cos(\alpha)}, \end{align}$
where $\alpha$ is the angle between $\bold{b_i}$ and $\bold{b_i^*}$ . (Note that $-\tfrac{\pi}{2} \leq \alpha \leq \tfrac{\pi}{2}$ beacuse of the way in which $\bold{b_i^*}$ is defined.) Let S_i denote the (n-1)-dimensional hyperplane spanned by the basis vectors $\bold{b_1},\ldots{},\bold{b_{i-1}},\bold{b_{i+1}},\ldots{},\bold{b_n}$ . Notice that $\bold{b_i^*}$ is perpendicular to S_i by definition. Thus, given that $\alpha$ is the angle between $\bold{b_i}$ and $\bold{b_i^*}$ , the angle between $\bold{b_i}$ and S_i is $\pi - \alpha$ . Thus, if $\beta = \pi - \alpha$ , Equation 2.5 becomes

If basis vector $\bold{b_i}$ is relatively dependent of the other vectors $\bold{b_j}, 1 \leq j \leq n, j \neq i$ , then the angle between $\bold{b_i}$ and the hyperplane S_i will be relatively small, and thus $\frac{1}{\sin(\beta)}$ will be large. Conversely, if $\bold{b_i}$ is relatively independent of the other basis vectors, $\beta$ will be close to $\frac{\pi}{2}$ radians, and the product $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ will be close to one^2.1. These geometric arguments lead directly to a measure which is a function of the products $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ where $1 \leq i \leq n$ . Since $\vert\beta_i\vert \leq \tfrac{\pi}{2}$ , we could choose the function $S_1(A) = \sum \Vert\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert = \sum \tfrac{1}{\sin(\beta_i)}$ as the measure function. Unfortunately, as Section 2.4.4 points out below, there is no simple formula for finding the optimal value of $\lambda$ for a row move involving the basis vectors $\bold{b_i}$ and $\bold{b_j}$ . Seysen is able to avoid these computational difficulties by using
$\begin{align*}S(A) & = \sum_{i=1}^n \Vert\bold{b_i}\Vert^2 \Vert\bold{b_i^*}\Vert^2, \\ & = \sum_{i=1}^n \frac{1}{\sin^2(\beta_i)}, \end{align*}$
as the measure function, which does yield a simple formula for $\lambda$ . Since $\sin(\beta_i) \in [0,1]$ , the squared terms in the S(A) function are guaranteed to be larger on a term-by-term basis than the corresponding terms in the S₁(A) sum. Thus, if lattice basis B₁ has smaller measure than basis B₂ using the S₁ measure function, B₁ will also have smaller measure than B₂ when compared using the Seysen measure S. An additional advantage to using a function of the $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ product terms is that bounds exists on the size of the individual terms. In [17] Håstad and Lagarias show that the following bound applies for some primal basis B and dual basis B^* of a given lattice:

This bound immediately implies that there exists a basis of L with Seysen measure bounded by $\exp(O(n^{\tfrac{1}{3}}))$ , since:
$\begin{align*}\max_{1 \leq i \leq n} \left\{ \Vert\bold{b_i}\Vert, \Vert\bold{b_... ...xp(O(n^{\frac{1}{3}})), \\ S(A) & \leq \exp(O(n^{\frac{1}{3}})). \end{align*}$
Seysen shows in [38] that the bound in Equation 2.6 may be improved to

which reduces the bound on S(A) for an S-reduced lattice to:
$\begin{align*}\sum_{i=1}^n \Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert & \leq n \... ...\exp(\ln n) \exp(O((\ln n)^2), \\ S(A) & \leq \exp(O((\ln n)^2). \end{align*}$
To date, this is the best known bound on the Seysen-measure of an S-reduced lattice basis. However, as is the case with the LLL algorithm, in some cases Seysen's algorithm produces S₂-reduced lattice bases which have measures much lower than the theoretical bound.

Choosing $\lambda$ Values

We now consider the choice of $\lambda$ values in Seysen's basis reduction algorithm. Assume that S(A) is as in Equation 2.3 above, and that only two-vector row moves are considered (i.e. transformation matrices of the form $T_{i,j}^\lambda$ for integer values of i,j and $\lambda$ ). We first show that

yields the maximum possible reduction in S(A) for fixed values of i and j where $\lambda \in {\Bbb R}$ . Further, we show that if we require $\lambda \in {\Bbb Z}$ , then

is indeed the value which yields the best possible reduction in the Seysen measure of the lattice basis. Let i,j be fixed integers with $1 \leq i,j \leq n$ ; $\bold{b_i}, \bold{b_j}, \bold{b_i^*}$ and $\bold{b_j^*}$ are the basis vectors on which we will perform a row move. Without loss of generality, we assume that $\lambda\bold{b_i}$ will be added to $\bold{b_j}$ and $\lambda\bold{b_j^*}$ will be subtracted from $\bold{b_i^*}$ . Define $\bold{b_j'}$ and $\bold{{b_i^*}'}$ to be the values of $\bold{b_j}$ and $\bold{b_i^*}$ after the row move is performed:
$\begin{align*}\bold{b_j'} & = \bold{b_j} + \lambda\bold{b_i}, \\ \bold{{b_i^*}'} & = \bold{b_i^*} - \lambda\bold{b_j^*}. \end{align*}$
Let A and A^* be the quadratic forms associated with the lattice and its dual before the row move occurs, and let A' and A^*' be the associated quadratic forms after the row move. Then
$\begin{align*}A' & = T_{j,i}^\lambda \;A \;T_{i,j}^\lambda, \\ {A^*}' & = T_{i,j}^{-\lambda} \;A^* \;T_{j,i}^{-\lambda}. \end{align*}$
Now, given that $T_{i,j}^\lambda$ transition matrices have exactly one off-diagonal nonzero entry, it is easy to see that A' differs from A only in the values in the $i^{\text{th}}$ row, the $j^{\text{th}}$ row, the $i^{\text{th}}$ column, and the $j^{\text{th}}$ column. The same is also true for A^*'. Since the Seysen measure function S(A) only depends upon the diagonal elements in A and A^*, we know that
$\begin{align}S(A') - S(A) & = \sum_{i=1}^n a_{i,i}' {a_{i,i}^*}' - \sum_{i=1}^n ... ...' + a_{j,j}'{a_{j,j}^*}' - a_{i,i} a_{i,i}^* - a_{j,j} a_{j,j}^*. \end{align}$
When A is right-multiplied by $T_{i,j}^\lambda$ , the $i^{\text{th}}$ column of A is added to the $j^{\text{th}}$ column of A. When this matrix is subsequently left-multiplied by $T_{j,i}^\lambda$ , the $i^{\text{th}}$ row is added to the $j^{\text{th}}$ row. Thus, after these two transformations, the value of a_i,i is unchanged, but

Using Equations 2.12 and 2.13, Equation 2.11 becomes:
$\begin{align*}S(A') - S(A) & = a_{i,i} \left( a_{i,i}^* - 2 \lambda a_{i,j}^* + ... ...j}^* + 2 \lambda a_{i,j} a_{j,j}^* - 2 \lambda a_{i,i} a_{i,j}^*. \end{align*}$
Differentiating with respect to $\lambda$ and setting the result equal to 0, we find that:
$\begin{align*}\frac{\partial}{\partial \lambda} \left(S(A') - S(A)\right) & = 4\... ...( \frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}} \right ). \end{align*}$
Thus, if $\lambda$ could take on any real value, for fixed i and j the minimum value of S(A') is obtained with $\lambda = \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right)$ . We have shown that the minimum value of S(A) with $\lambda \in {\Bbb R}$ is obtained when $\lambda$ satisfies Equation 2.8. Our goal now is to show that if $\lambda$ is restricted to integer values, Equation 2.9 yields that value of $\lambda$ for which S(A) is minimized. Let
$\begin{align*}\lambda & = \lambda_z + \lambda_r, \quad\text{where } \lambda_z \i... ...(i,j,\lambda) & = S(T_{j,i}^\lambda \;A \;T_{i,j}^\lambda) - S(A). \end{align*}$
We know that for fixed i,j, $\lambda = \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right)$ minimizes the value of $\Delta$ . Furthermore, as $\Delta$ is a quadratic function of $\lambda$ , at least one of $\lambda_z$ and $\lambda_z + 1$ must minimize $\Delta$ for fixed, integer values of $\lambda$ . Consider $\Delta(i,j,\lambda_z)$ and $\Delta(i,j,\lambda_z+1)$ :
$\begin{align*}\begin{split} \Delta(i,j,\lambda_z) & = 2 \lambda_z^2 a_{i,i} a_{... ...j,j}^* + 2 a_{i,j} a_{j,j}^* - 2 a_{i,i} a_{i,j}^*, \end{split} \end{align*}$
Thus,

As S(A) is a non-negative valued function which we want to minimize, we are interested in large, negative $\Delta$ values (i.e. $\vert\Delta\vert$ should be large, $\Delta < 0$ ). Thus, if Equation 2.14 is > 0, we should choose $\lambda = \lambda_z$ ; similarly, if Equation 2.14 is < 0, set $\lambda = \lambda_z + 1$ . When is Equation 2.14 greater than zero?
$\begin{align*}\Delta(i,j,\lambda_z + 1) - \Delta(i,j,\lambda_z) & > 0, \\ \Lon... ...frac{1}{2}, \\ \Longrightarrow \quad \lambda_r & < \tfrac{1}{2}. \end{align*}$
Thus, if $\lambda_r < \tfrac{1}{2}$ , then Equation 2.14 is positive, and we should choose $\lambda' = \lambda_z$ . If $\lambda > \tfrac{1}{2}$ , Equation 2.14 is negative, and we should set $\lambda' = \lambda_z + 1$ . Thus,
$\begin{align*}\lambda' & = \left\lceil \lambda_z + \lambda_r \right\rfloor, \\ ... ...j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right) \right\rfloor, \end{align*}$
which proves Equation 2.9.

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.

Lazy vs. Greedy Selection Methods

In Section 2.1.2 above we outlined the differences between lazy and greedy methods for selecting a row move to perform on each iteration of the Seysen while loop. In this section we describe the results of test lattice reductions on small-dimension lattices using both the lazy and greedy approaches. All experimental tests were performed on random integer lattices of determinant one. Integer lattice bases were generated as follows. Let B be an $n \times n$ integer matrix where the $i^{\text{th}}$ column of B corresponds to basis vector $\bold{b_i}$ . The elements of matrix B are:

The function $\operatorname{rand}(x)$ generates a random number chosen uniformly from the interval [0,x]; in these experiments x = 4. Notice that $\det(B) = 1$ since B is upper-triangular and all diagonal entries b_i,i = 1. To generate a random, dense lattice which is not upper-triangular yet still has determinant equal to 1, we perform random row moves on matrix B to generate matrix B'. We choose n² pairs of integers (i,j) with $1 \leq i,j \leq n$ and $i \neq j$ . For each such pair, $\lambda$ is chosen to be +1 or -1 with equal probability. Then, the current $\bold{b_i}$ is scaled by $\lambda$ and added to $\bold{b_j}$ . (That is, we set $B = B \;T_{i,j}^\lambda$ .) The result of these n² random row moves is matrix B', which is a basis for our test lattice L. Since $T_{i,j}^\lambda$ transformations preserve the determinant of the lattice, we know that $\det(L) = 1$ . We may thus measure the performance of Seysen's algorithm on lattice L by how close reduced lattice L' is to I_n.

**Table 2.1:** Comparison of Lazy and Greedy Selection Methods
n	Avg. # Steps (Lazy)	Avg. # Steps (Greedy)	Ratio (Lazy/Greedy)
20	2079.90	758.50	2.74
25	4096.40	1624.25	2.52
30	7444.80	3279.45	2.27
35	8787.35	3094.25	2.84

Table 2.1 summarizes the results of tests comparing the performance of lazy and greedy selection methods. Twenty test lattices were generated for each dimension $n \in \{20,25,30,35\}$ . In all cases where $n \leq 30$ , both lazy and greedy algorithms were able to completely reduce all test lattices to I_n. The table shows the average number of row moves required by the lazy and greedy methods to reduce a lattice to I_n. On average, the lazy selection scheme required over twice as many row reductions as the greedy scheme did to reduce a given test lattice. At n = 35 the lazy algorithm was able to reduce to I_n only two of the twenty attempted lattices; the remaining problems all encountered local minima during the reduction, thus halting Seysen's algorithm. The greedy implementation was unable to completely reduce any of the n = 35 test lattices. The two versions of the algorithm performed about equally well if we look at the Seysen measure of the reduced n = 35 test lattices. These experimental results tell us two things concerning the relative merits of lazy and greedy selection schemes. First, when both lazy and greedy methods are likely to produce lattice bases with similar Seysen measures, the greedy selection methods will save at least a factor of two in the number of reduction steps. Second, based on the n = 35 data, using greedy instead of lazy does not appear to significantly reduce the performance of the algorithm as a whole. For our test lattices neither method performed significantly better than the other in terms of the Seysen measure of the S₂-reduced lattice bases. One might argue that it is not reasonable to compare only the number of reduction steps required to reduce lattices using greedy and lazy selection methods, since that measure fails to take into account the cost of selecting the two basis vectors to reduce. A naive implementation of the greedy algorithm might require O(n²) time, as there are $\tfrac{1}{2}n(n-1)$ possible pairs of basis vectors $(\bold{b_i},\bold{b_j}), i \neq j$ which must be considered. However, it turns out that, after an initial O(n²) precomputation phase, only O(n) time is required to greedily select the next row move. Assume that we have computed $\Delta(i,j,\lambda(i,j))$ values for all pairs of integer $(i,j), 1 \leq i,j \leq n$ . Now, after a specific row move involving basis vectors i' and j' is performed, the only previously computed values of $\Delta$ which need to be updated are those for which i = i', i = j', j = i' or j = j'. (If you consider $\Delta$ to be an array of values, the $(i')^{\text{th}}$ and $(j')^{\text{th}}$ rows and columns of $\Delta$ are all that need to be recomputed.) Thus, this recomputation can be performed in O(n) time. Storing $\Delta$ values can reduce the cost of a greedy selection method from O(n²) to O(n). However, even O(n) cost would be prohibitive if the actual amount of computation required to select a pair of vectors was comparable to the cost of performing a row move. This is not the case; performing a row move requires O(n) multiprecision math operations, whereas the stored $\Delta$ values need only be stored as single- or double-precision floating point numbers. (The values are generally different enough that 32 or 64 bits will provide more than enough precision.) Since multiprecision operations take significantly more time than double-precision operations, and since each row-move requires O(n) operations, it seems reasonable to discount the added cost of performing the greedy selection as noise when compared to the cost of implementing the main portion of the algorithm. Based on these experimental results, we chose to use a greedy selection strategy in all subsequent implementations of Seysen's basis reduction algorithm. For lattices where we know that Seysen's algorithm will be able to perform a significant amount of basis reduction, such as the sparse lattices associated with subset sum problems (see Chapter 3), the greedy selection method and its expected reduced execution time are preferred.

Choosing $\lambda$ Values

As shown in the previous section, the selection method for choosing row moves in Seysen's algorithm can affect both the algorithm's performance and running time. In our comparison of lazy and greedy selection methods above, however, we implicitly sidestepped another such issue: the method by which values of $\lambda$ are chosen for a specific row move. Section 2.1.4 showed that for specified lattice basis vectors $(\bold{b_i},\bold{b_j})$ , the value of $\lambda$ which minimizes $\Delta(i,j,\lambda)$ is:

However, recall from Section 2.1.1 that any transformation matrix $T_{i,j}^\lambda$ may be represented as the product of $\lambda$ $T_{i,j}^{\pm 1}$ matrices (+1 if $\lambda >0$ , -1 otherwise). Thus, when a $T_{i,j}^\lambda$ transformation is applied to lattice basis B, we are implicitly performing $\lambda$ row moves at once. It may be the case that for some lattices, a finer degree of control is required; that is, a greedy algorithm might perform even better if it was restricted to performing only T_i,j¹ and T_i,j^-1 transformations. That way the algorithm would have the finest possible degree of control over row operations. It is also important to note that a greedy selection mechanism uses $\lambda$ values in two distinct places. First, in order to select a pair of basis vectors to reduce, the greedy approach calculates $\Delta(i,j,\lambda(i,j))$ for all possible values of $i,j, i \neq j$ ( $\lambda(i,j)$ is the function in Equation 2.15 above). Once a pair of vectors has been chosen, a $T_{i,j}^\lambda$ transformation is applied. In the first case, $\lambda$ is used as part of the scoring mechanism in order to choose a set of basis vectors to reduce. In the second case $\lambda$ plays a different role, the number of times to add vector $\bold{b_i}$ to $\bold{b_j}$ . Because $\lambda$ values have these two distinct functions, it is important that we distinguish between those roles when testing methods of choosing $\lambda$ values. We consider in this section three versions of Seysen's basis reduction algorithm and their performance on a set of randomly generated integer lattices^2.2. All three versions use a greedy selection scheme to choose the next row move to perform. They differ only in the set of allowed values of $\lambda$ in the scoring and transformation phases. These version are:

The $({\Bbb Z},{\Bbb Z})$ version is identical to our ``greedy'' implementation of the previous section; it will serve as our control. The $({\Bbb Z},\pm 1)$ version of Seysen's algorithm is designed to greedily select the best possible row move based on unlimited $\lambda$ values, but to perform the least possible number of changes to the lattice basis before recomputing what to do next. The $(\pm 1,\pm 1)$ version also restricts lattice basis changes to the minimum amount possible on each step, but this version selects a row move based only on what it can do immediately to reduce the S(A) measure, not on any ``future potential.''

Table 2.2: Comparison of $({\Bbb Z},{\Bbb Z})$ , $({\Bbb Z},\pm 1)$ and $(\pm 1,\pm 1)$ Options

n

L₁₀

S(A)

L₁₀^*

Method

L₁₀'

S(A')

L₁₀^*'

# Steps

$({\Bbb Z},{\Bbb Z})$

0.

20.

0.

757.4

20

82.4

$4.7 \cdot 10^{11}$

118.2

$({\Bbb Z},\pm 1)$

0.

20.

0.

767.0

$(\pm 1,\pm 1)$

0.

20.

0.

787.3

$({\Bbb Z},{\Bbb Z})$

0.

25.

0.

1622.1

25

132.0

$5.7 \cdot 10^{14}$

192.9

$({\Bbb Z},\pm 1)$

0.

25.

0.

1603.4

$(\pm 1,\pm 1)$

0.

25.

0.

1610.3

$({\Bbb Z},{\Bbb Z})$

0.

30.

0.

3275.3

30

195.8

$9.3 \cdot 10^{17}$

287.2

$({\Bbb Z},\pm 1)$

0.

30.

0.

3176.1

$(\pm 1,\pm 1)$

0.

30.

0.

3316.1

$({\Bbb Z},{\Bbb Z})$

110.4

$1.0 \cdot 10^8$

112.6

3037.0

35

269.2

$6.2 \cdot 10^{20}$

390.0

$({\Bbb Z},\pm 1)$

99.0

$4.0 \cdot 10^7$

102.2

3022.0

$(\pm 1,\pm 1)$

112.3

$1.3 \cdot 10^8$

114.6

2920.8

$({\Bbb Z},{\Bbb Z})$

216.9

$5.2 \cdot 10^{12}$

227.1

2240.2

40

343.8

$1.8 \cdot 10^{23}$

507.0

$({\Bbb Z},\pm 1)$

206.5

$1.6 \cdot 10^{12}$

217.0

2399.4

$(\pm 1,\pm 1)$

205.0

$1.5 \cdot 10^{12}$

217.3

2527.2

$({\Bbb Z},{\Bbb Z})$

304.6

$4.2 \cdot 10^{15}$

323.5

2369.9

45

434.0

$2.0 \cdot 10^{26}$

656.7

$({\Bbb Z},\pm 1)$

290.6

$1.2 \cdot 10^{15}$

312.3

2569.8

$(\pm 1,\pm 1)$

296.5

$1.9 \cdot 10^{15}$

315.8

2739.2

$({\Bbb Z},{\Bbb Z})$

402.8

$2.3 \cdot 10^{18}$

429.2

2698.1

50

541.2

$4.5 \cdot 10^{29}$

833.5

$({\Bbb Z},\pm 1)$

386.1

$6.3 \cdot 10^{17}$

418.4

3276.4

$(\pm 1,\pm 1)$

393.8

$1.1 \cdot 10^{18}$

422.4

3491.1

**Table 2.2:** Comparison of $({\Bbb Z},{\Bbb Z})$ , $({\Bbb Z},\pm 1)$ and $(\pm 1,\pm 1)$ Options
n	L₁₀	S(A)	L₁₀^*	Method	L₁₀'	S(A')	L₁₀^*'	# Steps
				$({\Bbb Z},{\Bbb Z})$	0.	20.	0.	757.4
20	82.4	$4.7 \cdot 10^{11}$	118.2	$({\Bbb Z},\pm 1)$	0.	20.	0.	767.0
				$(\pm 1,\pm 1)$	0.	20.	0.	787.3
				$({\Bbb Z},{\Bbb Z})$	0.	25.	0.	1622.1
25	132.0	$5.7 \cdot 10^{14}$	192.9	$({\Bbb Z},\pm 1)$	0.	25.	0.	1603.4
				$(\pm 1,\pm 1)$	0.	25.	0.	1610.3
				$({\Bbb Z},{\Bbb Z})$	0.	30.	0.	3275.3
30	195.8	$9.3 \cdot 10^{17}$	287.2	$({\Bbb Z},\pm 1)$	0.	30.	0.	3176.1
				$(\pm 1,\pm 1)$	0.	30.	0.	3316.1
				$({\Bbb Z},{\Bbb Z})$	110.4	$1.0 \cdot 10^8$	112.6	3037.0
35	269.2	$6.2 \cdot 10^{20}$	390.0	$({\Bbb Z},\pm 1)$	99.0	$4.0 \cdot 10^7$	102.2	3022.0
				$(\pm 1,\pm 1)$	112.3	$1.3 \cdot 10^8$	114.6	2920.8
				$({\Bbb Z},{\Bbb Z})$	216.9	$5.2 \cdot 10^{12}$	227.1	2240.2
40	343.8	$1.8 \cdot 10^{23}$	507.0	$({\Bbb Z},\pm 1)$	206.5	$1.6 \cdot 10^{12}$	217.0	2399.4
				$(\pm 1,\pm 1)$	205.0	$1.5 \cdot 10^{12}$	217.3	2527.2
				$({\Bbb Z},{\Bbb Z})$	304.6	$4.2 \cdot 10^{15}$	323.5	2369.9
45	434.0	$2.0 \cdot 10^{26}$	656.7	$({\Bbb Z},\pm 1)$	290.6	$1.2 \cdot 10^{15}$	312.3	2569.8
				$(\pm 1,\pm 1)$	296.5	$1.9 \cdot 10^{15}$	315.8	2739.2
				$({\Bbb Z},{\Bbb Z})$	402.8	$2.3 \cdot 10^{18}$	429.2	2698.1
50	541.2	$4.5 \cdot 10^{29}$	833.5	$({\Bbb Z},\pm 1)$	386.1	$6.3 \cdot 10^{17}$	418.4	3276.4
				$(\pm 1,\pm 1)$	393.8	$1.1 \cdot 10^{18}$	422.4	3491.1

Table 2.2 compares the performance of the $({\Bbb Z},{\Bbb Z})$ , $({\Bbb Z},\pm 1)$ and $(\pm 1,\pm 1)$ versions of Seysen's basis reduction algorithm. For each value of n, twenty test lattices of dimension n were generated and Seysen-reduced by each of the three methods. The table lists aggregate information for each value of n (all numbers shown are the geometric mean of the experimental values obtained for each of the twenty test lattices):

For $n \leq 30$ , all three implementation were able to completely reduce all test lattices to I_n. The only difference in the performance of the three methods was in the number of reduction steps required to reduce a test lattice, and these differences were minor (no more than 5% variation among any of the values for a given dimension). More differences among the methods appeared once $n \geq 35$ and Seysen's algorithm was no longer able to reduce any of the test lattices to I_n. For the majority of the test lattices, the $({\Bbb Z},\pm 1)$ appears to yield the most Seysen-reduced lattice basis, although it requires significantly more row moves to perform this reduction than the $({\Bbb Z},{\Bbb Z})$ method. This improvement is expected; after all, the only difference between the $({\Bbb Z},{\Bbb Z})$ and $({\Bbb Z},\pm 1)$ methods is that that latter looks more frequently at the lattice basis and takes smaller ``steps'' while performing a reduction. However, as the dimension of the lattice basis increased, the ratio of row moves required by $({\Bbb Z},\pm 1)$ to row moves required by $({\Bbb Z},{\Bbb Z})$ also increased. By the time n = 50, the $({\Bbb Z},\pm 1)$ method required approximately 30% more reduction steps to reduce test lattices than the $({\Bbb Z},{\Bbb Z})$ method did. The performance of the $(\pm 1,\pm 1)$ method fell somewhere between that of $({\Bbb Z},\pm 1)$ and $({\Bbb Z},{\Bbb Z})$ for test lattices with $n \geq 45$ . This is somewhat surprising in and of itself, since the capability of the $(\pm 1,\pm 1)$ method to consider future reduction is severely limited. This unexpected performance may be an artifact of our method of generating test lattices; we only performed n² row operations on the initial upper-triangular lattice basis and used only $T_{i,j}^{\pm 1}$ transitions to modify the lattice basis. This could account for the relatively good performance of the $(\pm 1,\pm 1)$ method, and also the differences between the $({\Bbb Z},{\Bbb Z})$ and $({\Bbb Z},\pm 1)$ methods. The experiments summarized in Table 2.2 do not indicate that any one of the tested methods consistently performs better than the others. Without any clear indication that one method would yield significantly better results (especially as $n \rightarrow 100$ ), we were reluctant to use any method in Seysen's algorithm except the $({\Bbb Z},{\Bbb Z})$ one implicitly defined by Seysen himself. For special types of lattices, it is probably worthwhile to compare these methods again. It may be that increased performance by the $({\Bbb Z},\pm 1)$ method more than offsets the increase in the number of row operations. However, for our experiments in subsequent sections (and the subset sum lattices of Chapter 3) we continued to use the $({\Bbb Z},{\Bbb Z})$ form of Seysen's algorithm.

Testing the $B_{\theta }$ Lattice

The previous sections detailed small tests which compared the relative performance of Seysen's algorithm when a few minor changes were made to its structure. In this section and the following one we investigate more fully the performance of the algorithm itself as a reduction technique for self-dual lattice bases and random integer lattices. Our next series of tests was suggested by J. C. Lagarias (personal communication) to test the self-dual reduction performance of the algorithm. Let $B_\theta, 0 < \theta < \tfrac{1}{2}$ be the lattice basis consisting of the following basis vectors:
$\begin{align*}\bold{b_1} & = (1,0,0,0,\ldots{}), \\ \bold{b_2} & = (\theta,1,0... ... \bold{b_4} & = (\theta,-\theta,\theta,1,\ldots{}), \\ & \cdots \end{align*}$
If $B_{\theta }$ is represented as a matrix with $\bold{b_i}$ as the $i^{\text{th}}$ column, then we have:

Basis $B_{\theta }$ has the property that $\Vert\bold{b_i^*}\Vert$ grows exponentially with n, but rather slowly for small dimensions.

Table 2.3: Performance of Seysen's Algorithm on $B_{\theta }$ for $\theta = 0.4, 5 \leq n \leq 105$

n

L₁₀

S(A)

L₁₀^*

L₁₀'

S(A')

L₁₀^*'

# Steps

5

0.30

7.36e+00

0.50

0.30

6.59e+00

0.30

3

10

1.10

3.65e+01

3.80

1.10

1.61e+01

1.00

12

15

2.30

1.88e+02

10.60

2.10

2.78e+01

1.90

29

20

3.70

1.00e+03

21.10

3.40

4.28e+01

3.10

45

25

5.30

5.37e+03

35.20

4.90

5.80e+01

4.20

70

30

7.10

2.89e+04

53.00

6.30

7.88e+01

6.20

135

35

9.10

1.55e+05

74.40

8.20

1.03e+02

8.00

177

40

11.20

8.35e+05

99.50

10.40

1.30e+02

9.90

240

45

13.40

4.49e+06

128.30

13.10

1.72e+02

12.80

363

50

15.70

2.42e+07

160.70

15.80

2.32e+02

16.90

509

55

18.20

1.30e+08

196.70

18.60

2.62e+02

18.30

698

60

20.70

6.99e+08

236.40

22.30

3.53e+02

22.50

772

65

23.30

3.76e+09

279.70

25.00

4.01e+02

25.70

1067

70

25.90

2.02e+10

326.80

26.40

4.40e+02

28.10

1467

75

28.70

1.09e+11

377.40

32.70

6.93e+02

36.60

1702

80

31.50

5.85e+11

431.70

31.90

6.00e+02

35.70

2123

85

34.40

3.15e+12

489.70

35.70

7.25e+02

40.40

2775

90

37.30

1.69e+13

551.30

39.70

8.50e+02

45.40

3345

95

40.30

9.10e+13

616.60

44.10

1.03e+03

51.00

4839

100

43.30

4.89e+14

685.60

49.00

1.20e+03

55.50

6363

105

46.40

2.63e+15

758.10

50.80

1.19e+03

56.70

8303

**Table 2.3:** Performance of Seysen's Algorithm on $B_{\theta }$ for $\theta = 0.4, 5 \leq n \leq 105$
n	L₁₀	S(A)	L₁₀^*	L₁₀'	S(A')	L₁₀^*'	# Steps
5	0.30	7.36e+00	0.50	0.30	6.59e+00	0.30	3
10	1.10	3.65e+01	3.80	1.10	1.61e+01	1.00	12
15	2.30	1.88e+02	10.60	2.10	2.78e+01	1.90	29
20	3.70	1.00e+03	21.10	3.40	4.28e+01	3.10	45
25	5.30	5.37e+03	35.20	4.90	5.80e+01	4.20	70
30	7.10	2.89e+04	53.00	6.30	7.88e+01	6.20	135
35	9.10	1.55e+05	74.40	8.20	1.03e+02	8.00	177
40	11.20	8.35e+05	99.50	10.40	1.30e+02	9.90	240
45	13.40	4.49e+06	128.30	13.10	1.72e+02	12.80	363
50	15.70	2.42e+07	160.70	15.80	2.32e+02	16.90	509
55	18.20	1.30e+08	196.70	18.60	2.62e+02	18.30	698
60	20.70	6.99e+08	236.40	22.30	3.53e+02	22.50	772
65	23.30	3.76e+09	279.70	25.00	4.01e+02	25.70	1067
70	25.90	2.02e+10	326.80	26.40	4.40e+02	28.10	1467
75	28.70	1.09e+11	377.40	32.70	6.93e+02	36.60	1702
80	31.50	5.85e+11	431.70	31.90	6.00e+02	35.70	2123
85	34.40	3.15e+12	489.70	35.70	7.25e+02	40.40	2775
90	37.30	1.69e+13	551.30	39.70	8.50e+02	45.40	3345
95	40.30	9.10e+13	616.60	44.10	1.03e+03	51.00	4839
100	43.30	4.89e+14	685.60	49.00	1.20e+03	55.50	6363
105	46.40	2.63e+15	758.10	50.80	1.19e+03	56.70	8303

Tests were performed on $B_{\theta }$ lattices with $\theta = 0.4$ using Seysen's basis reduction algorithm for dimensions $5 \leq n \leq 105$ . Based on the experimental results of Sections 2.2.1 and 2.2.2 above, we used a greedy selection method to choose which pairs of vectors to reduce on each iteration of the algorithm, and $\lambda$ was allowed to be any integer value during all stages of the algorithm. The results of these tests are given in Table 2.3. For each test lattice, the following information is given:

The exponential growth of $\Vert\bold{b_i^*}\Vert$ may be easily seen by looking at the rate of growth of the L₁₀^* column in the tables. Remember that L₁₀^* is the sum of the base 10 logarithms of the lengths of the dual basis vectors. This sum grows at least linearly with respect to n; thus, the $\Vert\bold{b_i^*}\Vert$ grow exponentially in n.

**Figure 2-1:** Performance of Seysen's Algorithm on B_0.4 Lattice: L₁₀^* and L₁₀^*' vs. n
$\begin{figure} \hspace{\fill} \epsffile{kz-comp-1.ps} \hspace{\fill} \end{figure}$

For the $B_{\theta }$ lattice Seysen's basis reduction algorithm yields little improvement in the vector lengths $\Vert\bold{b_i}\Vert$ . Indeed, for some values of n we have L₁₀ < L₁₀'. This is not the case, though, for the dual lattice; Seysen's reduction algorithm greatly decreases the lengths of the vectors in the dual basis. When the algorithm completes, we have $L_{10}' \approx {L_{10}^*}'$ and the lengths of the vectors in the prime and dual lattice bases are comparable. Figure 2-1 shows graphically the improvement made by Seysen's algorithm to $\Vert\bold{b_i^*}\Vert$ . The results obtained from application of Seysen's algorithm to $B_{\theta }$ lattices are quite promising. The algorithm was able to significantly reduce the lengths of the dual basis vectors $\bold{b_i^*}$ without significantly increasing the lengths of the basis vectors for $B_{\theta }$ themselves. In fact, the resulting primal and dual bases have basis vector lengths which are comparable. Certainly this suggests that Seysen's algorithm is a viable technique for applications in which we wish to simultaneously reduce a lattice and its dual.

Testing Random Integer Lattices

The reductions of $B_{\theta }$ lattices tested application of Seysen's algorithm to a very narrow class of lattices. From a cryptographic point of view (see Chapter 3 below), and in many other cases, our goal is to reduce random lattices with integer basis vectors. In general, we do not know that our lattice conforms to some specific structure; we are give only the basis vectors themselves. Thus, it is appropriate to investigate the performance of Seysen's algorithm on randomly generated integer lattices. When we considered in Section 2.2.1 the choice of a lazy or greedy selection method for Seysen's algorithm, we ran tests on random integral lattices L with $\det(L) = 1$ of small dimension ( $n \leq 35)$ . We utilize the same technique for generating random lattices as used before, except now we consider lattices up to dimension 50. In addition to running Seysen's algorithm over these test cases, each lattice was also reduced using the LLL algorithm with $y \lesssim 1.0$ . Table 2.4 summarizes the results of these experiments. For each value of $n \equiv 0 \bmod 5$ , $20 \leq n \leq 50$ , twenty different test lattices were generated. The columns n, L₁₀, S(A), L₁₀^*, L₁₀', S(A'), and L₁₀^*' identify the same quantities as in Table 2.2 above. The column labeled ``# Steps (Seysen)'' reports the average number of reduction steps (row moves) performed by Seysen's algorithm for each test lattice. The average number of row operations performed by the LLL algorithm is listed in the ``# Steps (Lovasz)'' column. (LLL reduction was not performed on lattices with $n \geq 45$ because of the excessive amount of computer time required to obtain results).

Table 2.4: Performance of Seysen's Algorithm on Random Integer Lattices

n

L₁₀

S(A)

L₁₀^*

L₁₀'

S(A')

L₁₀^*'

# Steps
(Seysen)

# Steps
(Lovasz)

20

82.37

$4.71 \cdot 10^{11}$

118.22

0. (20)

20.

0.

757.37

4424.0

25

131.95

$5.67 \cdot 10^{14}$

192.93

0. (20)

25.

0.

1622.11

12977.4

30

195.81

$9.28 \cdot 10^{17}$

287.24

0. (20)

30.

0.

3275.30

32718.5

31

205.86

$3.05 \cdot 10^{18}$

308.06

0. (20)

31.

0.

3690.51

38085.2

32

222.41

$1.04 \cdot 10^{19}$

323.66

0. (11)

1695.8

0.

3626.00

44770.0

33

237.86

$5.07 \cdot 10^{19}$

348.19

0. (5)

86999.0

0.

3408.27

53407.4

34

243.86

$4.48 \cdot 10^{19}$

358.86

0. (1)

$4.26 \cdot 10^6$

0.

3075.63

60299.7

35

269.25

$6.24 \cdot 10^{20}$

390.02

110.39

$1.00 \cdot 10^8$

112.57

3036.95

70047.2

36

287.16

$5.26 \cdot 10^{21}$

423.62

138.11

$2.48 \cdot 10^9$

141.13

2738.39

80836.3

37

291.86

$5.23 \cdot 10^{21}$

438.94

162.17

$3.20 \cdot 10^{10}$

167.33

2400.10

91491.5

38

310.35

$3.17 \cdot 10^{22}$

469.18

175.52

$1.07 \cdot 10^{11}$

182.50

2520.02

103624.0

39

329.32

$1.78 \cdot 10^{23}$

500.89

196.26

$7.45 \cdot 10^{11}$

203.87

2555.72

118338.0

40

343.84

$1.82 \cdot 10^{23}$

507.02

216.88

$5.21 \cdot 10^{12}$

227.10

2240.23

132901.0

45

434.01

$2.02 \cdot 10^{26}$

656.67

304.56

$4.20 \cdot 10^{15}$

323.53

2369.90

-

50

541.20

$4.53 \cdot 10^{29}$

833.54

402.80

$2.33 \cdot 10^{18}$

429.15

2698.11

-

**Table 2.4:** Performance of Seysen's Algorithm on Random Integer Lattices
n	L₁₀	S(A)	L₁₀^*	L₁₀'	S(A')	L₁₀^*'	# Steps (Seysen)	# Steps (Lovasz)
20	82.37	$4.71 \cdot 10^{11}$	118.22	0. (20)	20.	0.	757.37	4424.0
25	131.95	$5.67 \cdot 10^{14}$	192.93	0. (20)	25.	0.	1622.11	12977.4
30	195.81	$9.28 \cdot 10^{17}$	287.24	0. (20)	30.	0.	3275.30	32718.5
31	205.86	$3.05 \cdot 10^{18}$	308.06	0. (20)	31.	0.	3690.51	38085.2
32	222.41	$1.04 \cdot 10^{19}$	323.66	0. (11)	1695.8	0.	3626.00	44770.0
33	237.86	$5.07 \cdot 10^{19}$	348.19	0. (5)	86999.0	0.	3408.27	53407.4
34	243.86	$4.48 \cdot 10^{19}$	358.86	0. (1)	$4.26 \cdot 10^6$	0.	3075.63	60299.7
35	269.25	$6.24 \cdot 10^{20}$	390.02	110.39	$1.00 \cdot 10^8$	112.57	3036.95	70047.2
36	287.16	$5.26 \cdot 10^{21}$	423.62	138.11	$2.48 \cdot 10^9$	141.13	2738.39	80836.3
37	291.86	$5.23 \cdot 10^{21}$	438.94	162.17	$3.20 \cdot 10^{10}$	167.33	2400.10	91491.5
38	310.35	$3.17 \cdot 10^{22}$	469.18	175.52	$1.07 \cdot 10^{11}$	182.50	2520.02	103624.0
39	329.32	$1.78 \cdot 10^{23}$	500.89	196.26	$7.45 \cdot 10^{11}$	203.87	2555.72	118338.0
40	343.84	$1.82 \cdot 10^{23}$	507.02	216.88	$5.21 \cdot 10^{12}$	227.10	2240.23	132901.0
45	434.01	$2.02 \cdot 10^{26}$	656.67	304.56	$4.20 \cdot 10^{15}$	323.53	2369.90	-
50	541.20	$4.53 \cdot 10^{29}$	833.54	402.80	$2.33 \cdot 10^{18}$	429.15	2698.11	-

The LLL basis reduction algorithm was able to reduce all tested lattice bases to the n-dimensional cubic lattice basis (i.e. B' = I_n), which has Seysen measure zero. Seysen's algorithm performed similarly on all lattice bases with $n \leq 31$ . (Values in parentheses in the L₁₀' column indicate the number of lattice bases which were Seysen-reduced to the n-dimensional cubic lattice.) For $32 \leq n \leq 34$ the Seysen algorithm was able to completely reduce only some of the attempted lattice bases; no lattice basis with $n \leq 35$ was ever reduced by the Seysen algorithm to I_n. The degradation in the performance of Seysen's algorithm as n increases from 30 to 35 is quite surprising. Apparently, for these types of lattices, the probability of reaching a lattice basis which is a local minimum of the Seysen measure function increases substantially over that range. The LLL reduction algorithm does not exhibit any decrease in performance, except for an overall increase in the number of reduction steps required to convert the given lattice basis into the n-dimensional cubic lattice basis. Of course, the LLL algorithm does take significantly longer to run than the Seysen algorithm, but these tests suggest that Seysen's algorithm alone will not be sufficient to reduce lattice bases in higher dimensions. We may need to combine Seysen's algorithm with other lattice basis reduction techniques to efficiently reduce large lattice bases. Alternately, it may be possible to use some heuristic technique to reduce the probability of reaching a lattice basis which is a local minimum of S(A), or to ``kick'' a Seysen-reduced basis out of a local minimum. The following section suggests a few possible methods which may be employed when Seysen's algorithm fails to S-reduce a lattice basis and stops at a local minimum of S(A).

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.

Row Moves Involving Three or Four Vectors

As initially described in [38], Seysen's basis reduction algorithm only considers row moves involving two basis vectors. That is, we only consider moves of the form:

(These moves, of course, correspond to the set of transformation matrices $T_{i,j}^\lambda$ .) However, there is no real theoretical reason to restrict ourselves to row moves of the form given in Equation 2.16. We consider here possibilities for row moves of the form
$\begin{align*}\bold{b_j} & \leftarrow \bold{b_j} + \lambda \bold{b_{i_1}} + \kap... ...mbda \bold{b_{i_1}} + \kappa \bold{b_{i_2}} + \mu \bold{b_{i_3}}, \end{align*}$
and their dual basis counterparts
$\begin{align*}\bold{b_j^*} & \leftarrow \bold{b_j^*} + \lambda \bold{b_{i_1}^*} ... ...bold{b_{i_1}^*} + \kappa \bold{b_{i_2}^*} + \mu \bold{b_{i_3}^*}. \end{align*}$
Before we begin, it should be noted that there are practical reasons for not considering row moves involving more than two vectors at any given time. First, if we are using a greedy selection method to choose the vectors upon which to operate, more work is required to choose the correct n-tuple. (If we use a lazy implementation this is less of a concern). Second, 2-moves^2.3 exhibit a symmetry between the prime and dual lattice which is lost when we consider n-moves with n > 2. When we perform a $T_{i,j}^\lambda$ transformation, $\bold{b_j} \leftarrow \bold{b_j} + \lambda\bold{b_i}$ and $\bold{b_i^*} \leftarrow \bold{b_i^*} - \lambda\bold{b_j^*}$ . Thus we need not explicitly consider operations on the dual lattice, since every dual lattice transformation has an equivalent transformation in the prime lattice (with i,j swapped and $\lambda$ multiplied by -1). For n-moves with n > 2, however, this duality is lost. The 3-move

for example, has the following effects in the dual basis:
$\begin{align*}\bold{b_{i_1}^*} & \leftarrow \bold{b_{i_1}^*} - \lambda \bold{b_j... ...ld{b_{i_2}^*} & \leftarrow \bold{b_{i_2}^*} - \kappa \bold{b_j^*}. \end{align*}$
Thus, even if we use a lazy approach to choose which vectors to use in a row operation, there are many more candidate operations which must be considered since there is no longer any overlap between moves in the primal and dual lattices. Calculating the best possible values of $\lambda, \kappa, \mu,\ldots{}$ for a given set of basis vectors is also more complicated as the number of vectors involved in the move increases. As an example, let us consider the computation required to choose $\lambda$ and $\kappa$ for the 3-move
$\begin{align*}\bold{b_j} & \leftarrow \bold{b_j} + \lambda \bold{b_{i_1}} + \kap... ...ld{b_{i_2}^*} & \leftarrow \bold{b_{i_2}^*} - \kappa \bold{b_j^*}. \end{align*}$
We assume without loss of generality that i₁ < i₂ < j. Then we may represent this transformation by a $T_{i_1,i_2,j}^{\lambda,\kappa}$ transformation matrix, where:

Now, we compute the partial derivatives of $\Delta(i_1,i_2,j,\lambda,\kappa)$ with respect to $\kappa$ and $\lambda$ ,
$\begin{align*}\frac{\partial}{\partial \kappa} \Delta(i_1,i_2,j,\lambda,\kappa) ... ...2 a_{i_1,i_2} a_{j,j}^* \kappa + 4 a_{i_1,i_1} a_{j,j}^* \lambda, \end{align*}$
set them equal to 0, and solve for $\kappa$ and $\lambda$ :
$\begin{gather*}\frac{\partial \Delta}{\partial \kappa} = 0, \frac{\partial \Delt... ...2})^2 (a_{j,j}^*)^2 - 16 a_{i_1,i_1} a_{i_2,i_2} (a_{j,j}^*)^2}. \end{gather*}$
If we wish to implement a version of Seysen's algorithm which allows 3-moves in general, we must calculate six sets of ( $\lambda,\kappa$ ) values; one set for each of

Clearly including the six possible 3-moves and the eight possible 4-moves in Seysen's algorithm is computationally expensive. However, there are reasons for wishing to do so. When Seysen's algorithm reaches a local minimum of S(A) for some lattice L it is reducing, it has reached a point where any single row move increases S(A). By allowing the algorithm to look at 3-moves when it has run out of 2-moves to perform, we increase the number of configurations Seysen's algorithm must investigate before it gives up. It is quite possible that one or more configurations which are 3-move attainable but not 2-move attainable will have Seysen measure smaller than S(A). These reduced lattices would then permit the algorithm to move out of the local minimum and continue its reduction steps. We added routines to our implementation of Seysen's basis reductions algorithm to implement three- and four-vector row operations. In all cases one vector was designated the ``target'' vector and integer multiples of the other two or three vectors were added to the target. We did not notice any significant improvement in the performance of the algorithm on random integer lattices of determinant 1 when these additional moves were allowed to occur on any iteration of the algorithm. In some cases, the greedy selection scheme actually performed worse when allowed to use 3-moves and 4-moves; usually this decrease in performance occurred because the algorithm ``jumped ahead'' too quickly by using the 3-move and would have done better by using a sequence of 2-moves. Three- and four-vector operations were helpful, however, when a lattice reduction reached a local minimum. In many of these cases a few 3-moves (or 4-moves, if considered) existed which would carry the lattice out of the local minimum and allow the algorithm to resume processing. Given these experiences and the increased complexity required to operation on more than two vectors at a time, we would suggest using n-moves when n > 2 only to move the lattice being reduced out of a local minimum.

Simulated Annealing and Rapid Quenching

Many combinatorial optimization problems have been successfully attacked using simulated annealing, which was initially developed independently by [10,21]. Simulated annealing approaches resemble local optimum algorithms, except that a random component is introduced which allows occasional ``uphill'' moves (moves which worsen the current solution to the problem according to a cost schedule). As simulated annealing methods have been successfully applied to a wide variety of problems, it seems reasonable to consider adding simulated annealing techniques to Seysen's algorithm in the hope of reducing the number of lcoal minima which cause the algorithm to stop before reaching a global minimum. Modifying Seysen's algorithm to work along the lines of a simulated annealing approach would not be difficult. In the implementation of the algorithm, we simply need to accept row moves which increase the Seysen measure of the lattice basis. The probability of accepting a move which increases S(A) will depend upon the temperature of the reduced lattice, which starts high and decreases according to some cooling schedule and the reduction proceeds. It thus remains to specify the initial temperature of a lattice basis, the probability (as a function of temperature) of accepting a row move which increases S(A), and a cooling schedule which describes how temperature decreases with time/reduction steps. Another technique, based on physical systems, for solving combinatorial optimization problems is the rapid quenching approach. Simulated annealing slowly reduces the temperature of the solution, thus gradually reducing the probability of accepting a move to a higher energy/cost state. Rapid quenching, on the other hand, quickly reduces the temperature in the model, bringing the system to a minimum quickly. The system is then reheated to a temperature lower than the initial temperature, and the process is repeated. Seysen's algorithm itself can be viewed as one iteration of a rapid quenching process. The heated system is the initial lattice basis, and the algorithm itself, by greedily reducing the Seysen measure of the lattice basis, decreases the temperature of the system. We modified our implementation of Seysen's algorithm to simulate multiple rapid quenching iterations. When a lattice basis reached a minimum of the Seysen measure function and no single two-vector row move could decrease S(A), a randomization function was performed on the lattice to ``heat'' it and Seysen's algorithm was subsequently applied to the heated lattice basis. Our randomizing function chose a linear number of pairs of vectors $(\bold{b_i},\bold{b_j}), i \neq j$ , and (with equal probability) either added $\bold{b_i}$ to or subtracted $\bold{b_i}$ from $\bold{b_j}$ . (This is the same randomizing operation used previously to generate random integer lattices, except that we perform O(n) randomizations here instead of O(n²) as was done before.) Multiple iterations of the heating/Seysen-reducing process did successfully reduce lattice bases more than Seysen-reduction alone, although it is unclear as to how much benefit can be gained from repeated applications of this process.

Using Hadamard Matrices to Permute Lattice Bases

Our third and last suggestion for moving lattice bases out of local minima was suggested by Matthijs Coster (personal communication). Instead of randomly permuting the lattice basis as random quenching does, Coster suggests using a Hadamard matrix H to transform a Seysen-reduced lattice basis B into lattice basis $B' = B \;H$ . Recall that matrix H is a Hadamard matrix if it satisfies the following two properties:

It is not difficult to show that if H is an $n \times n$ Hadamard matrix, then n = 2 or $n \equiv 0 \bmod 4$ ([1], 2.21 Exercise 10). Now, consider the lattice basis B' obtained by multiplying B by a Hadamard matrix H. (If $n \not\equiv 0 \bmod 4$ we may consider B and the corresponding lattice L to be sublattices of an n'-dimension space with $n' > n, n' \equiv 0 \bmod 4$ .) Each basis vector in B' is a linear combination of all the basis vectors in B, but no two B' vectors have similar constructions, since $\bold{h_i}$ and $\bold{h_j}$ differ in $\tfrac{1}{2}n$ coordinates if $i \neq j$ . The basis vectors in B' will have lengths $\approx \sqrt{n}$ times the lengths of the basis vectors in B, so while we obtain a good randomization of the lattice, the lengths of the basis vectors are still manageable. We should point out that the matrix H is not a linear transformation matrix; $\det(H) \neq 1$ . This means that the lattice generated by B is not the same lattice generated by B'. However, all n-dimensional Hadamard matrices H_n satisfy:

and the net result of the operation is to scale B (and the associated lattice L) by a factor of n. Thus we can divide out the factor of n and we are left with the lattice L we started with. So, our plan of attack should be as follows. When Seysen's algorithm stops and reports that lattice basis B is a local minimum of S(A), create $B' = B \;H$ where H is a Hadamard matrix. Now, Seysen-reduce lattice basis B' until a local minimum is reached. Then compute $B'' = \tfrac{1}{n} B' H_n^t$ . Finally, Seysen-reduce basis B'', producing basis B'''. Bases B and B''' describe the same lattice L. Note that there is no guarantee that S(A''') < S(A), where A,A''' and the quadratic forms associated with B,B''' respectively. Further study is required before we may conclude whether Hadamard permutations provide a reasonable method for ``kicking'' lattice basis B.

Extending Seysen's Algorithm

The description Seysen gave in [38] of his algorithm was only an outline of a lattice basis reduction technique. We have tried in this chapter to give both theoretical and empirical reasons for the choices made in implementing Seysen's algorithm. However, we have only touched upon a few of the many possible combinations of techniques. As the next chapter shows, these choices are effective as reducing lattice bases derived from subset sum problems. For other lattices, their effectiveness may be in question. We briefly mention here some of the other possible choices for the various components of Seysen's algorithm.

General n-vector Row Operations

Section 2.3.1 above discussed the possibility of extending Seysen's algorithm to consider row operations involving three and four vectors at once. It is possible to extend these operations to encompass arbitrary k-moves where integer multiples of k-1 basis vectors are added to another basis vector. For fixed k, let $\bold{b_j}$ be the target basis vector (the vector to be modified) and let $\bold{b_{i_1}},\ldots{},\bold{b_{i_{k-1}}}$ be the basis vectors to be added to $\bold{b_i}$ in multiples of $\lambda_1,\ldots{},\lambda_{k-1}$ respectively. Then, after the row move, we will have:
$\begin{align*}\bold{b_j} & \leftarrow \bold{b_j} + \sum_{m=1}^{k-1} \lambda_m \... ...^*} - \lambda_m \bold{b_j^*}, \quad\text{for } 1 \leq m \leq k-1. \end{align*}$
Now, we may solve for the new values of the quadratic forms A and A^* after the row move has occurred. In A, the only value that changes is a_j,j. Its new value is:

In the dual lattice quadratic form A^*, the values a_{i_m,i_m}^* change for $1 \leq m \leq k-1$ . Their new values are:

If we compute $\Delta$ , the change in S(A) resulting from this row move, we find that:
$\begin{align}\begin{split} \Delta & = a_{j,j}^* \left( \left( \sum_{m=1}^{k-1} ... ...{Sb}^{k-1} \lambda_m \lambda_p a_{i_m,i_p} a_{j,j}^*. \end{split} \end{align}$
Thus, for all $1 \leq m \leq k-1$ we have:

We may thus compute formulae for all $\lambda_m$ for $1 \leq m \leq k-1$ if we solve the simultaneous system of equations obtained by setting the k-1 derivatives defined in Equation 2.21 equal to zero. Of course, we still must solve the problem of finding optimal integer values for the $\lambda_m$ . For the 2-move case we showed that $\lceil \lambda_r \rfloor$ was the best integer choice for $\lambda$ . It is not clear that rounding will work in the k-move case. The real values derived for the $\lambda_m$ may only indicate some range of integer values which need to be searched.

Alternate Selection Criteria

Seysen's original implementation of his basis reduction algorithm used a ``lazy'' approach for choosing pairs of basis vectors to reduce. Pairs of integers $(i,j), 1 \leq i,j \leq n$ were searched in lexicographic order until a suitable row move involving $\bold{b_i}$ and $\bold{b_j}$ was found. We have presented above empirical evidence which favors a ``greedy'' approach, even when the extra computation time required to implement the ``greedy'' method is considered. Selection methods other than the ``greedy'' and ``lazy'' approaches were not considered in our experiments, but are certainly possible. For example, in addition to taking into account the reduction in S(A) which will result from a row move, we might also wish to consider the other row moves which will be blocked by performing this move. That is, if $\lambda \bold{b_j}$ is added to $\bold{b_i}$ , the potential S(A) reductions of all other row moves which involve either $\bold{b_i}$ or $\bold{b_j}$ will be modified. Perhaps we should choose row moves so that the moves they block have minimum S(A) reduction potential. We could combine this idea with the ``greedy'' method; selecting a row move with the greatest difference between the amount it reduces S(A) and the average S(A) reduction of all the moves it blocks.

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:

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.

Alternate S(A) Functions

Section 2.1.3 above gave reasons for using functions of the product terms $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ . In particular, the function

was selected as the Seysen measure function because it yielded a closed form solution for the optimal value of $\lambda$ given i and j. However, other functions could certainly be employed as the method of comparing different lattice bases. In this section we briefly describe how Seysen's algorithm would have to be modified to accommodate another measure function. We restrict our attention to versions of Seysen's algorithm which use only row moves involving two basis vectors (i.e. $\bold{b_j} \leftarrow \bold{b_j} + \lambda\bold{b_i}$ ). Recall that the formula in Equation 2.9 for the optimal choice of $\lambda$ was derived by maximizing the change in the Seysen measure function caused by a row move involving two particular basis vectors. In the Seysen measure function is changed, the only direct impact it will have upon the operation of the algorithm is that the optimal value of $\lambda$ for basis vectors $(\bold{b_i},\bold{b_j})$ will be computed in a different manner. In [38] Seysen mentions two possible replacements for the S(A) function:
$\begin{align*}S_1(A) & = \prod_{i=1}^n a_{i,i} a_{i,i}^* = \prod_{i=1}^n \Vert\... ...i}^*} = \sum_{i=1}^n \Vert\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert. \end{align*}$
Replacing S(A) with S₁(A) implies that our choice of $\lambda$ must minimize:
$\begin{align*}\Delta(i,j,\lambda) & = S_1(T_{j,i}^\lambda \;A \;T_{i,j}^\lambda)... ...{j,j} {a_{j,j}^*}' - a_{i,i} a_{i,i}^* a_{j,j} a_{j,j}^* \right). \end{align*}$
Solving $\frac{\partial \Delta}{\partial \lambda} = 0$ yields an extremely complex expression for $\lambda$ . Similar results occur when we try to substitute S₂(A) for S(A). In both cases, no simple closed-form solution for $\lambda$ exists as was the case with S(A). It may be still be possible to utilize measure functions in Seysen's algorithm with no simple closed-form solution for $\lambda$ if we are willing to sacrifice some performance. If the range of possible integer $\lambda$ values is bounded, for given i and j we can compute $\Delta(i,j,\lambda)$ for all possible $\lambda$ values in the permitted range. The $\lambda$ which provides the greatest change may then be selected. The cost of this procedure is that we can no longer guarantee that the maximal $\lambda$ for a pair of basis vectors $(\bold{b_i},\bold{b_j})$ may be found in constant time. If the range of $\lambda$ values to consider is usually small, then we will probably notice little more than a linear slowdown in the running time of the algorithm. For large ranges of possible $\lambda$ values, further heuristics might be applied, such as only considering $\lambda$ values which are near a power of two. In our experiments we noticed that large $\lambda$ values tended to occur only during the first few row reduction performed by Seysen's algorithm. After this initial burst in reduction of S(A) row moves tended only to involve small integer $\lambda$ values; it was quite rare to find $\vert\lambda\vert > 10$ . If similar conditions occur for the lattice bases in question, it is probably reasonable to use a more complex measure function than S(A) and use a small exhaustive search over a bounded range of possible $\lambda$ values to find the optimal $\lambda$ coefficient for a row move.

Introduction

Point Lattices

Reduced Lattice Bases

Lattice Basis Reduction Algorithms

The Seysen Basis Reduction Algorithm

Theoretical Analysis

Sufficiency of Matrices

Choosing Vector Pairs to Reduce

The S(A) Function

Choosing Values

Empirical Analysis

Lazy vs. Greedy Selection Methods

Choosing Values

Testing the Lattice

Testing Random Integer Lattices

When Seysen's Algorithm Fails

Row Moves Involving Three or Four Vectors

Simulated Annealing and Rapid Quenching

Using Hadamard Matrices to Permute Lattice Bases

Extending Seysen's Algorithm

General n-vector Row Operations

Alternate Selection Criteria

Alternate Choices of

Alternate S(A) Functions

Bibliography

Sufficiency of $T_{i,j}^\lambda$ Matrices

Choosing $\lambda$ Values

Choosing $\lambda$ Values

Testing the $B_{\theta }$ Lattice

Alternate Choices of $\lambda$