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:

$$\lambda = \left\lceil \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right) \right\rfloor.$$ (2.12)

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:

1.

$({\Bbb Z},{\Bbb Z})$: $\lambda$ may take on any integer value when choosing a set of basis vectors for the next row move, and any $T_{i,j}^\lambda$ may be performed on those vectors.

2.

$({\Bbb Z},\pm 1)$: $\lambda$ may take on any integer value when choosing a set of basis vectors for the next row move. However, only T_i,j¹ and T_i,j^-1 actual transformations are allows. (If $\lambda >0$ we add $\bold{b_i}$ to $\bold{b_j}$. If $\lambda <0$ we subtract $\bold{b_i}$ from $\bold{b_j}$.)

3.

$(\pm 1,\pm 1)$: $\lambda$ may only be $\pm 1$ when choosing the next row move, and only $T_{i,j}^{\pm 1}$ transformations may be performed on the basis.

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	L10	S(A)	L10*	Method	L10'	S(A')	L10*'	# 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):

• n: The dimension of the test lattice in this group.
• L₁₀: $\sum_{i=1}^n \log_{10} \Vert\bold{b_i}\Vert$ before reduction.
• S(A): The Seysen measures before reduction.
• L₁₀^*: $\sum_{i=1}^n \log_{10} \Vert\bold{b_i^*}\Vert$ before reduction.
• Method: The restructions placed of $\lambda$ values.
• L₁₀': $\sum_{i=1}^n \log_{10} \Vert\bold{b_i}\Vert$ after reduction.
• S(A'): The Seysen measure after reduction.
• L₁₀^*': $\sum_{i=1}^n \log_{10} \Vert\bold{b_i^*}\Vert$ after reduction.
• # Steps: The number of row moves performed during the reduction.

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.