Previous Empirical Methods

Along with their theoretical results, Lagarias and Odlyzko [26] presented in 1985 the results of the first empirical attacks on general subset sum problems. Their method was to apply a multiprecision version of the LLL algorithm to the basis L presented in Section 3.2 above ( $\bold{b_{n+1}}=(0,0,0,\ldots{},0,s)$). Lagarias and Odlyzko set the LLL parameter y=1, which they said yielded better results than y=0.75 but tripled execution time in practice. Also, five random orderings of the basis vectors for lattice L were tried, since different initial orderings yield different LLL-reduced bases. Experiments were conducted on various subset sum problems with $n \leq 50$ and densities d between 0.5 and 0.875. Figure 3-1 graphically shows the performance of the Lagarias-Odlyzko method. For each tested value of n, the labeled curve connects (density,success rate) points in the plot obtained by attempting to solve subset sum problems of size n.

  

Figure 3-1: Lagarias-Odlyzko Results: Success Rate vs. Density

For $n \leq 26$, the LLL algorithm appeared to function almost as well as a square-norm lattice oracle; all subset sum problems with density $d \leq 0.6408\ldots{}$ and $n \leq 26$ were solved when LLL was used on five random permutations of the basis vectors. However, performance degrades quickly as n grows above 30. For n=40, Lagarias and Odlyzko were able to solve all attempted subset sum problems only for density 0.5. At n=50, only two-thirds of the attempted density 0.5 problems were solved. In [33] Radziszowski and Kreher reported the results of extensive attempts to solve subset sum problems. Their reduction algorithm, based on LLL, differed from that used in Lagarias-Odlyzko in two important ways. First, Radziszowski and Kreher modified the LLL algorithm to reduce the number of required multiprecision calculations. In essence, instead of running LLL once on a lattice with numbers k bits long, they ran LLL m times with numbers k/m bits long (a divide-and-conquer approach). This modification sped up their algorithm and allowed them to attack larger subset sum problems than Lagarias and Odlyzko (larger here means greater value of n). The second change Radziszowski and Kreher made to the Lagarias-Odlyzko attack was to use another algorithm in conjunction with LLL to find short vectors in the lattice. This second algorithm, called Weight-Reduction, searches for pairs of vectors $(\bold{b_i},\bold{b_j})$ in the lattice for which:

$$\Vert\bold{b_i} + \epsilon \bold{b_j}\Vert < \max\{\Vert\bold... ...,\Vert\bold{b_j}\Vert\}, \quad\text{for } \epsilon = \pm 1.$$ (3.6)

When Weight-Reduction finds such a pair, it replaces the larger of $\bold{b_i}$ and $\bold{b_j}$ (in terms of square-norm) by the sum $\bold{b_i} + \epsilon \bold{b_j}$. Equation 3.6 is satisfied by a pair $(i,j), i \neq j$ if and only if

   $$\max \{\Vert\bold{b_i}\Vert^2,\Vert\bold{b_j}\Vert^2\} < 2 \cdot \Vert(\bold{b_i},\bold{b_j})\Vert.$$

The Weight-Reduction algorithm can easily be implemented in O(n²) time to search for all pairs of vectors $(\bold{b_i},\bold{b_j})$ which satisfy Equation 3.7.

  

Figure 3-2: Radziszowski-Kreher Inner Loop

Radziszowski and Kreher alternated calls to the modified LLL algorithm with calls to Weight-Reduction and a sorting procedure to improve the search for short vectors in the lattice. Figure 3-2 is a flowchart-like representation of the process. The initial basis L is LLL-reduced (y=0.99 for all invocations of LLL). The output of LLL is then Weight-Reduced, sorted by length, and then fed back into LLL. This process continues until some termination condition is met. In theory, ``no decrease in $\sum_{i=1}^n \Vert\bold{b_i}\Vert$'' could be used as the termination condition. In their experiments, Radziszowski and Kreher set an explicit bound on the maximum number of loops which could be performed. The output of this iterative process is then Weight-Reduced one more time. One important feature of the Radziszowski-Kreher loop is the insertion of the sorting phase before LLL is run each time. By sorting the vectors in the lattice by length, the length of the shortest vector in L is guaranteed not to increase by application of LLL. If L is a lattice output by the sort procedure, then vector $\bold{b_1}$ in L is the shortest vector in the lattice. Now, LLL can replace $\bold{b_1}$ with some vector $\bold{b_2'}$ only if $\Vert\bold{b_2'}\Vert < \Vert\bold{b_1}\Vert$. (This does not hold for $\bold{b_i}$ in general but is true for $\bold{b_1}$.) Thus, we are guaranteed that the shortest vector in L before LLL is applied will not disappear from the basis unless an even shorter vector is found.

  

Figure 3-3: Radziszowski-Kreher Results: Success Rate vs. Density

Figure 3-3 shows graphically the results of the experiments carried out in [33]. For these experiments, only 15 loop iterations were allowed (9 if all the vectors in the basis were of length $< \tfrac{1}{2}n$). For values of $n \leq 34$, this algorithm was able to solve all attempted subset sum problems of density $d \leq 0.654$, which is above the Lagarias-Odlyzko bound. As n increases from 42 to 98 the density at which all attempted problems were solved decreases. As was reported in [26], the effectiveness of LLL as a lattice oracle drops off as the size of the lattice grows. Radziszowski and Kreher's results show however that it is possible to increase the effective range of LLL by combining it with other heuristic techniques. The Radziszowski-Kreher algorithm was the best known method to date for solving subset sum problems. In the following section, we show how to to combine the Seysen basis reduction algorithm with the LLL algorithm, other heuristics, and the theoretical improvements in [12] (Section 3.2) to greatly extend the range of subset sum problems which may be empirically attacked and successfully solved.