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:

$$B_\theta = \left[ b_{i,j} \right]_{1 \leq i,j \leq n} = \begi... ...}, \\ (-1)^{j-i+1}\theta & \text{if $i < j$ }. \end{cases}$$

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

• n: The dimension of the lattice.
• L₁₀: $\sum_{i=1}^n \log_{10} \Vert\bold{b_i}\Vert$ before reduction.
• S(A): The Seysen measure of $B_{\theta }$ before reduction.
• L₁₀^*: $\sum_{i=1}^n \log_{10} \Vert\bold{b_i^*}\Vert$ before reduction.
• L₁₀': $\sum_{i=1}^n \log_{10} \Vert\bold{b_i}\Vert$ after reduction.
• S(A'): The Seysen measure of $B_{\theta }$ 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.

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

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.