Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems.

C. P. Schnorr M. Euchner Universität Frankfurt Fachbereich Mathematik/Informatik Postfach 111932 6000 Frankfurt am Main Germany

July 1993

Abstract

We report on improved practical algorithms for lattice basis reduction. We propose a practical floating point version of the L^{3}–algorithm of Lenstra, Lenstra, Lovász (1982). We present a variant of the L^{3}– algorithm with “deep insertions” and a practical algorithm for block Korkin–Zolotarev reduction, a concept introduced by Schnorr (1987). Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up to 66 random weights of arbitrary bit length within at most a few hours on a UNISYS 6000/70 or within a couple of minutes on a SPARC 1+ computer.

1 Introduction and Survey

It is a major open problem to determine the exact complexity of finding short vectors in a lattice. On the one hand the problem of finding a non–zero lattice vector that is shortest in the sup–norm is known to be NP–complete [4] (in its feasibility recognition form). On the other hand the L^{3}–lattice basis reduction algorithm of Lenstra, Lenstra, Lovász [17] is a polynomial time algorithm that finds a non–zero vector in an m–dimensional lattice that is guaranteed to be at most 2^{m/2}–times the length of the shortest non– zero vector in that lattice. The L^{3}–algorithm finds in practice much shorter vectors than is guaranteed by the worst case 2^{m/2}–bound. The performance of the L^{3} has been further improved by suitable modifications [5,15,22], and new algorithms are being invented [19,23,24,27]. Possibly finding reasonably short vectors in a random lattice is not so difficult on the average. This would have important consequences for solving linear and non–linear integer programming problems.

Several attempts have been made to improve on the performance of the L^{3}–algorithm for lattice reduction. Recently Seysen [27] and Schnorr [23,24] have invented new algorithms for basis reduction in the square norm. Seysen’s method performs extremely well for lattices of dimension up to 30. It operates on small integers, the intermediate integers for Seysen’s algorithm are not larger than the input integers. Schnorr [23] has extended the L^{3}– reduction to a hierarchy of polynomial time reduction algorithms that find a non–zero vector in an m–dimensional lattice that is guaranteed to be at most (1 + ε)^{m}–times the length of the shortest non–zero vector in that lattice. The degree of the polynomial that bounds the running time increases as ε converges to zero. A different approach to improve on lattice reduction has been made by Lovász and Scarf (1992). They propose a generalised lattice reduction algorithm that works for an arbitrary norm. This general approach is tailor–made for certain integer programming problems.

A bottleneck for the speed of the L^{3}–algorithm is the required exact arithmetic on large integers. Most of these arithmetic steps occur in the process of Gram–Schmidt orthogonalizing the basis vectors. It has been proposed to perform this orthogonalization in floating point arithmetic while keeping the basis vectors in exact integer representation. This however makes the L^{3}–algorithm unstable.

In this paper we present a practical floating point L^{3}–algorithm, L^{3}F P, having good stability according to empirical tests up to dimension 125 with integer entries of bit length up to 300. We also propose a practical algorithm for block Korkin–Zolotarev reduction and we introduce the variant of the L^{3}–algorithm that uses “deep insertions”. These algorithms produce considerably shorter lattice vectors than the original L^{3}–algorithm. They perform well in practice but may be inefficient in worst case. We report on the performance of all these algorithms in solving subset sum problems. These algorithms have also been applied to solve the diophantine approximation problem that yields the factorization of a given integer [25]. However to make this approach work for large integers further progress in basis reduction is needed.

The knapsack or subset sum problem is to solve, given positive integers a_{1}, …, a_{n} and s, the equation

∑_{i=1}^{n} a_{i}x_{i} = s with x_{1}, …, x_{n} ∈ {0, 1}.

The Brickell [1] and the Lagarias–Odlyzko [14] algorithms solve almost all subset sum problems for which the density d = n / log_{2} max a_{i} is sufficiently small. Radziszowski and Kreher [17] evaluate the performance of an improved variant of the Lagarias–Odlyzko algorithm. In this paper we replace in the Lagarias–Odlyzko method the L^{3}–algorithm, by more powerful reduction algorithms, namely by the L^{3}–algorithm with “deep insertions” and by block Korkin–Zolotarev reduction. We also replace the Lagarias–Odlyzko lattice by a lattice (1) – see section 7 – that is better suited to produce 0, 1–solutions for the knapsack equation. Empirical tests show that these algorithms solve almost all subset sum problems that have either sufficiently low or sufficiently high density. The hardest subset sum problems turn out to be those that have a density that is slightly larger than 1, i.e. a density about 1 + (log_{2}(n/2))/n. The new lattice basis (1) and the stronger reduction algorithms lead to a substantially improved success rate of subset sum algorithms. Using block Korkin–Zolotarev reduction with block size 20 we can solve almost all subset sum problems of dimension up to 58 even if their density is close to 1. It has been proved rigorously that for almost all subset sum problems with density less that 0.9408 the shortest non–zero vector in the associated lattice basis (1) yields a solution of the subset sum problem [3]. In section 6 we describe a particular practical algorithm for block Korkin– Zolotarev reduction. Using the improved reduction algorithms we can solve a much larger class of subset sum problems than was previously possible. Some empirical data are given in section 7. Several alternative algorithms for block Korkin–Zolotarev reduction and more empirical data are given in the master thesis of M. Euchner [5]. Another empirical comparison of the success rates for the new lattice basis (1) versus the Lagarias–Odlyzko lattice has been done by LaMacchia [15]. His success rates roughly correspond to our success rates using the weakest of our reduction methods, L^{3}–reduction in floating point arithmetic (algorithm L^{3}F P), see the comments in section 7.

Early versions of the new practical algorithms and the improved lattice (1) have been developed during the courses on lattice basis reduction which the first author gave at Frankfurt University in summer 1990. This work has been mentioned in the talk of the first author at the workshop on cryptography at Princeton University in September 1990 and has influenced the subsequent work in [3,10,15].

2 Basic concepts, L^{3}–reduction

Let IR^{n} be the n–dimensional real vector space with the ordinary inner product < , > and Euclidean length ∥y∥ = ⟨y, y⟩^{1/2}. A discrete, additive subgroup L ⊂ IR^{n} is called a lattice. Every lattice L is generated by some set of linearly independent vectors b_{1}, …, b_{m} ∈ L, called a basis of L,

L = {t_{1}b_{1} + ⋯ + t_{n}b_{m} | t_{1}, …, t_{m} ∈ ZZ}.

Let L(b_{1}, …, b_{m}) denote the lattice with basis b_{1}, …, b_{m}. Its rank or dimension is m and the determinant is defined as d(L) = det[⟨b_{i}, b_{j}⟩_{1≤i,j≤m}]^{1/2}. The rank and the determinant of the lattice do not depend on the choice of the basis. Let b_{1}, …, b_{m} ∈ IR^{n} be a basis of lattice L then b̄_{1}, …, b̄_{m} is another basis of L if and only if there exists a matrix T ∈ GL_{m}(ZZ) such that

[b_{1}, …, b_{m}] = [b̄_{1}, …, b̄_{m}] T.

Here [b_{1}, …, b_{m}] denotes the n×m matrix in M_{n,m}(IR) with column vectors b_{1}, …, b_{m}. The goal of lattice basis reduction is to transform a given lattice basis into a basis that consists of short vectors or, equivalently, into a basis consisting of vectors that are pairwise nearly orthogonal.

With an ordered lattice basis b_{1}, …, b_{m} ∈ IR^{n} we associate the Gram–Schmidt orthogonalization b̂_{1}, …, b̂_{m} ∈ IR^{n} which can be computed from b_{1}, …, b_{m} together with the Gram–Schmidt coefficients μ_{i,j} = ⟨b_{i}, b̂_{j}⟩ / ⟨b̂_{j}, b̂_{j}⟩ by the recursion

b̂_{1} = b_{1}, b̂_{i} = b_{i} − ∑_{j=1}^{i−1} μ_{i,j}b̂_{j} for i = 2, …, m.

We have μ_{i,i} = 1 and μ_{i,j} = 0 for i < j. The vectors b̂_{1}, …, b̂_{m} are linearly independent, they are not necessarily in the lattice. If the basis b_{1}, …, b_{m} is integral, i.e. b_{1}, …, b_{m} ∈ ZZ^{n}, then the vectors b̂_{1}, …, b̂_{m} and the coefficients μ_{i,j} are rational. We can write the above equations in matrix notation as

[b_{1}, …, b_{m}] = [b̂_{1}, …, b̂_{m}] [μ_{i,j}]_{1≤i,j≤m}^{⊤}.

An ordered basis b_{1}, …, b_{m} ∈ IR^{n} is called size–reduced if

|μ_{i,j}| ≤ 1/2 for 1 ≤ j < i ≤ m.

An individual basis vector b_{i} is size–reduced if |μ_{i,j}| ≤ 1/2 for 1 ≤ j < i.

Let δ be a constant, 1/4 < δ ≤ 1. Following [17] we call a basis b_{1}, …, b_{m} ∈ IR^{n} L^{3}–reduced with δ if it is size–reduced and if

δ ∥b̂_{k−1}∥^{2} ≤ ∥b̂_{k} + μ_{k,k−1}b̂_{k−1}∥^{2} for k = 2, …, m.

For practical purposes we are interested in a constant δ that is close to 1, e.g. δ = 0.99.

Let λ_{1}, …, λ_{m} denote the successive minima of lattice L, λ_{i} = λ_{i}(L) is defined as the smallest radius r of a ball that is centered at the origin and which contains r linearly independent lattice vectors. Any L^{3}–reduced basis consists of relatively short lattice vectors.

Theorem 1 [17] Every basis b_{1}, …, b_{m} that is L^{3}–reduced with δ satisfies

α^{1−i} ≤ ∥b_{i}∥^{2} λ_{i}^{−2} ≤ α^{m−1} for i = 1, …, m with α = (δ − 1/4)^{−1}.

The case δ = 3/4 of Theorem 1 has been settled in [17]. This proof can easily be extended to all δ, 1/4 < δ ≤ 1.

We next describe some basic reduction algorithms. We restrict ourselves to integer input bases. For a real number r let ⌈r⌋ ∈ ZZ denote the nearest integer, ⌈r⌋ = ⌈r−1/2⌉, with ⌈r⌋ = r−1/2 for half integers r ∈ (2ZZ+1)/2.

Algorithm for size–reduction of the basis vector b_{k} . INPUT b_{1}, …, b_{m} ∈ ZZ^{n} (a lattice basis)

μ_{i,j} for 1 ≤ j < i ≤ m (its Gram–Schmidt coefficients)

FOR j = k − 1, …, 1 DO

IF |μ_{k,j}| > 1/2 THEN [ b_{k} := b_{k} − ⌈μ_{k,j}⌋ b_{j} ,

FOR i = 1, …, m DO μ_{k,i} := μ_{k,i} − ⌈μ_{k,j}⌋ μ_{j,i} ]

OUTPUT b_{1}, …, b_{m} (basis where b_{k} is size–reduced)

μ_{i,j} for 1 ≤ j < i ≤ m (its Gram–Schmidt coefficients)

We obtain a size–reduced basis b_{1}, …, b_{m} by size–reducing each vector individually. Size–reducing the vector b_{k} does not affect the size–reduction of the other vectors.

Algorithm for L^{3}–reduction (according to [17]) INPUT b_{1}, …, b_{m} ∈ ZZ^{n} (a lattice basis), δ with 1/4 < δ < 1. (initiation) k := 2 (k is the stage)

compute the Gram–Schmidt coefficients μ_{i,j} for 1 ≤ j < i ≤ m and ∥b̂_{i}∥^{2} for i = 1, …, m.

WHILE k ≤ m DO size–reduce the vector b_{k} and update μ_{k,j} for j = 1, …, k − 1.

IF δ ∥b̂_{k−1}∥^{2} > ∥b̂_{k}∥^{2} + μ_{k,k−1}^{2}∥b̂_{k−1}∥^{2}
THEN [swap b_{k} and b_{k−1}, k := max(k − 1, 2)]
ELSE k := k + 1

OUTPUT b_{1}, …, b_{m} (a basis that is L^{3}–reduced with δ).

REMARKS 1. Upon entry of stage k the basis b_{1}, …, b_{k−1} is L^{3}–reduced with δ.

2. For every swap of b_{k−1}, b_{k} we must update ∥b̂_{k}∥^{2}, ∥b̂_{k−1}∥^{2} and μ_{i,ν}, μ_{ν,i} for ν = k, k − 1 and i = 1, …, m, see [17].

3. In the original L^{3}–algorithm only the first step b_{k} := b_{k} − ⌈μ_{k,k−1}⌋b_{k−1} of size–reducing b_{k} is done before the IF step and the size–reduction of b_{k} is completed before incrementing k to k + 1.

4. Let B denote max(∥b_{1}∥^{2}, …, ∥b_{m}∥^{2}) for the input basis. Throughout the algorithm the bit length of the numerators and denominators of the rational numbers ∥b̂_{i}∥^{2}, μ_{i,j} is bounded as O(m log B). The bit length of the coefficients of the b_{i} ∈ ZZ^{n} is also bounded as O(m log B) throughout the algorithm [17].

5. The algorithm terminates after at most ({m \atop 2}) log_{1/δ} B iterations. It performs at most O(m^{3} n log B) arithmetic operations on integers that are O(m log B) bits long, see [17].

In practical applications the above L^{3}–algorithm is suffering from the slowness of the subroutines for long integer arithmetic. To speed up the algorithm it has been proposed to operate the numbers μ_{i,j} and ∥b̂_{i}∥^{2} in floating point arithmetic. Then however the above algorithm becomes unstable and it has to be rewritten to minimize floating point errors. This will be done in section 3.

3 L^{3}–reduction using floating point arithmetic

In the following algorithm for L^{3}–reduction we keep the basis vectors b_{1}, …, b_{m} ∈ ZZ^{n} in exact representation and the numbers μ_{i,j}, ∥b̂_{i}∥^{2} in floating point. The basis must be exact since errors in the basis change the lattice and cannot be corrected. All other errors can be corrected using a correct basis. The following provisions are taken to minimize the floating point errors. We let v′ denote the floating point value corresponding to an exact value υ. Let the integer τ denote the number of precision bits in the floating point arithmetic.

1. Whenever we enter stage k we compute from the actual basis vectors b_{1}, …, b_{k} the numbers μ_{k,j} for j = 1, …, k − 1 and also c_{k} = ∥b̂_{k}∥^{2}. This will correct these values since the vectors b_{1}, …, b_{k} are exact.

2. If a large reduction coefficient, |⌈μ_{k,j}⌋| > 2^{τ/2}, occurs during the size– reduction of b_{k} then we subsequently decrease the stage k to k − 1. This will correct the coefficients μ_{k−1,j} and μ_{k,j} for j = 1, …, k − 1 as well as c_{k−1}, c_{k}, b′_{k−1}, b′_{k}.

3. If |⟨b′_{k}, b′_{j}⟩| < 2^{−τ/2} ∥b′_{k}∥ ∥b′_{j}∥ then we compute ⟨b_{k}, b_{j}⟩′ instead of ⟨b′_{k}, b′_{j}⟩. Since the leading bits in the computation of ⟨b′_{k}, b′_{j}⟩ cancel out the value ⟨b′_{k}, b′_{j}⟩ is too inexact.

Algorithm L^{3}FP, L^{3}–reduction in floating point arithmetic INPUT b_{1}, …, b_{m} ∈ ZZ^{n} (a lattice basis), δ with 1/2 < δ < 1.

1. (initiation) k := 2, F_{c} := false (k is the stage. The following values are available upon entry of stage k: μ_{i,j} for 1 ≤ j < i < k and c_{i} = ∥b̂_{i}∥^{2} for i = 1, …, k − 1) FOR i = 1, …, m DO b′_{i} := (b_{i})′

2. WHILE k ≤ m DO

(computation of μ_{k,1}, …, μ_{k,k−1}, c_{k} = ∥b̂_{k}∥^{2})

c_{k} := ∥b′_{k}∥^{2}, IF k = 2 THEN c_{1} := ∥b′_{1}∥^{2}

FOR j = 1, …, k − 1 DO
IF |⟨b′_{k}, b′_{j}⟩| < 2^{−τ/2} ∥b′_{k}∥ ∥b′_{j}∥
THEN s := ⟨b_{k}, b_{j}⟩′
ELSE s := ⟨b′_{k}, b′_{j}⟩

μ_{k,j} := (s − ∑_{i=1}^{j−1} μ_{j,i} μ_{k,i} c_{i})/c_{j}

c_{k} := c_{k} − μ_{k,j}^{2} c_{j}

3. (size–reduction of b_{k})

FOR j = k − 1, …, 1 DO

IF |μ_{k,j}| > 1/2 THEN
μ := ⌈μ_{k,j}⌋
IF |μ| > 2^{τ/2} THEN F_{c} := true
FOR i = 1, …, j − 1 DO μ_{k,i} := μ_{k,i} − μμ_{j,i}
μ_{k,j} := μ_{k,j} − μ, b_{k} := b_{k} − μ b_{j}, b′_{k} := (b_{k})′
END if |μ_{k,j}|
IF F_{c} THEN [ F_{c} := false, k := max(k − 1, 2), GOTO 2 ]

4. (swap b_{k−1}, b_{k} or increment k)

IF δ c_{k−1} > c_{k} + μ_{k,k−1}^{2} c_{k−1}

THEN [ swap b_{k}, b_{k−1} swap b′_{k}, b′_{k−1}
k := max(k − 1, 2) ]
ELSE k := k + 1

OUTPUT b_{1}, …, b_{m} (a basis that is L^{3}–reduced with δ).

COMMENTS. 1. According to our experience the algorithm L^{3}F P has good stability even for single precision floating point arithmetic and for very large input vectors. Double precision arithmetic results in a considerable decrease of the number of swaps and in a faster algorithm. The point is that L^{3}F P performs reduction with respect to the leading bits of the basis vectors handling about τ of these bits at the same time, where τ is the number of precision bits of the floating point arithmetic. Thus the number of swaps in L^{3}F P is proportional to log_{2} B/τ times the number of swaps in the L^{3}– algorithm.

2. We cannot prove that L^{3}F P always terminates. If the floating point precision is too small compared to the length of the input vectors L^{3}F P might run into cycles that are caused by floating point errors. However the algorithm was successful in several thousand applications with lattices of rank up to 125 and where the bit length of the input integers was up to 300.

3. Schnorr [24] has given an algorithm for L^{3}–reduction with provably negligible floating point errors. Practical versions of this algorithm are about 10% slower than the above algorithm L^{3}F P. The reduction algorithm in [24] uses the coefficients ν_{i,j} of the inverse matrix [ν_{i,j}] = [μ_{i,j}]_{1≤i,j≤m}^{−1}. It corrects floating point errors via the scalar products ⟨b_{i}, b_{j}⟩.

4. The flag F_{c} is set true if a correction step has to be performed. In this case k will be decreased to k − 1 and the μ_{i,j}, ∥b_{i}∥^{2} will be corrected for i = k − 1 and i = k.

5. To offset small floating point errors one has to use δ–values that are larger than 1/4, e.g. δ ≥ 1/2.

The following “deep insertion” step extends the swap b_{k} ↔ b_{k−1} of the L^{3}– algorithm. By replacing Step 4 of algorithm L^{3}F P by the “deep insertion” step we obtain a variant of L^{3}F P that finds shorter lattice vectors.

New Step 4 (deep insertion of b_{k})

c := ∥b′_{k}∥^{2}, i := 1

WHILE i < k DO
IF δ c_{i} ≤ c
THEN [ c := c − μ_{k,i}^{2} c_{i}, i := i + 1 ]
ELSE [ (b_{1}, …, b_{k}) := (b_{1}, …, b_{i−1}, b_{k}, b_{i}, …, b_{k−1})

rearrange the b′_{j} accordingly k := max(i − 1, 2), GOTO 2 ]

k := k + 1

COMMENTS. 1. A deep insertion possibly inserts b_{k} at some position i < k and increments the indices of the old vectors b_{i}, …, b_{k−1} by 1. The position i is chosen as the minimal i which results in decreasing c_{i} = ∥b̂_{i}∥^{2} by at least a factor δ. Throughout Step 4 c is the length square of the vector b̂_{i}^{new} in case that a deep insertion step of b_{k} at position i is performed.

2. Algorithm L^{3}F P with deep insertions may be super–polynomial time in worst case. If the deep insertions are only performed in case that either i ≤ c_{o} or k − i ≤ c_{o} for a fixed constant c_{o} then the deep insertion variant of L^{3}F P remains polynomial time.

4 L^{3}–reduction of a linearly dependent generator system

We can extend algorithm L^{3}F P so that it transforms every generator system b_{1}, …, b_{m} ∈ ZZ^{n} of a lattice into an L^{3}–reduced basis. If the vectors b_{1}, …, b_{m} are linearly dependent then the associated Gram–Schmidt orthogonalization b̂_{1}, …, b̂_{m} contains at least one zero–vector, which leaves us with another problem.

We must avoid increasing the stage to k +1 in case that c_{k} = ∥b̂_{k}∥^{2} is zero because then a division with c_{k} is done on the next stage k +1. Fortunately, if c_{k} is zero the condition δc_{k−1} > c_{k} + μ_{k,k−1}^{2}c_{k−1} for swapping b_{k−1}, b_{k} is satisfied since we have μ_{k,k−1}^{2} < 1/4 and δ ≥ 1/2. If k > 2 this swap of b_{k−1}, b_{k} and the decrease of k will avoid a subsequent division by zero. However if k = 2 and c_{2} = 0 swapping b_{2}, b_{1} may result in a zero–vector b_{1}. We can simply eliminate this zero–vector b_{1} from the basis. Going one step further we check after each size–reduction of b_{k} in Step 3 of L^{3}F P whether the reduced vector b_{k} is zero and in this case we eliminate b_{k} from the basis. This will correctly deal with all cases provided that initially b_{1} is not the zero–vector.

Thus we insert into Step 3 of L^{3}F P after the reduction of b_{k} and before changing k the following assignment:

Additional assignment for Step 3 of L^{3}FP IF b_{k} = 0 THEN [ eliminate b_{k}, m := m − 1, k := 2, GOTO 2 ]

We suppose that this assignment is always included in L^{3}F P if the input vectors b_{1}, …, b_{m} are linearly dependent. We call the algorithm L^{3}F P with the additional assignment the extended L^{3}F P.

Remarks. 1. The initial comments and the termination of the extended L^{3}F P (which is proved in Theorem 2 below) show that the extended L^{3}F P is correct up to floating point errors. It is sufficient to note that the vectors b_{1}, …, b_{k−1} of Stage k are always L^{3}–reduced with δ and that the algorithm terminates on Stage m+1. Thus the output vectors b_{1}, …, b_{m} form a basis that is L^{3}–reduced with δ.

2. Since the vectors b_{1}, …, b_{k−1} of Stage k are L^{3}–reduced with δ we see from Theorem 1 that c_{j} ≥ α^{1−j}∥b_{1}∥^{2} holds for j = 1, …, k − 1 where α = 1/(δ − 1/4) ≤ 4. Therefore the divisors c_{j} of Step 2 are sufficiently apart from 0. This helps to minimize floating point errors.

3. Resetting the stage k to 2, in the additional assignment for step 3, is a precaution against floating point errors. The generation of a zero–vector b_{k} produces some floating point errors that are due to the fairly small vectors b̂_{i} occuring within this process.

We present an upper bound on the number of swaps b_{k−1} ↔ b_{k} in the extended L^{3}F P relying on the following integer quantity D:

D = ∏_{b̂_{i}≠0} D_{i} with D_{i} = det L(b_{1}, …, b_{i})^{2} ,

where i ranges over all indices 1 ≤ i ≤ m − 1 with b̂_{i} ≠ 0. The quantity D extends the corresponding D in [17] to the case of linearly dependent input vectors b_{1}, …, b_{m}.

Theorem 2 If the extended L^{3}F P is performed in exact arithmetic we have that

1. every swap b_{k−1} ↔ b_{k} achieves D^{new} ≤ δ D^{old},

2. the total number of swaps b_{k−1} ↔ b_{k} is at most \binom{m}{2} log_{1/δ} B where B is the maximum length square ∥b_{i}∥^{2} of the input vectors b_{i} ∈ ZZ^{n} for i = 1, …, m.

Proof. 1. A swap of the vectors b_{k−1}, b_{k} leaves D_{i} for i ≠ k − 1 unchanged. If b̂_{k−1}^{new} ≠ 0 then b̂_{i}^{new}, b̂_{i}^{old} are zero for the same i. We have

D^{new} = D^{old} ∥b̂_{k−1}^{new}∥^{2} ∥b̂_{k−1}^{old}∥^{−2} ≤ δ D^{old}

since the swap reduces ∥b̂_{k−1}∥^{2} at least by a factor δ. This proves the claim for the case that b̂_{k−1}^{new} ≠ 0. In the case b̂_{k−1}^{new} = 0 we have b̂_{k}^{old} = 0 and thus

D^{old} = ∏_{i≠k} D_{i}^{old}, D^{new} = ∏_{i≠k−1} D_{i}^{new}

D^{new} / D^{old} = D_{k}^{new} / D_{k−1}^{old}.

Now the lattice L(b_{1}, …, b_{k−1}^{old}) has the same rank as the lattice L(b_{1}, …, b_{k−1}^{old}, b_{k}^{old}) = L(b_{1}, …, b_{k−1}^{new}, b_{k}^{new}) and it is properly contained in the latter lattice. This is because b_{k}^{old} ∉ L(b_{1}, …, b_{k−1}^{old}), which holds since b_{k}^{old} is size–reduced and b_{k}^{old} ≠ 0. The proper inclusion of the above lattice and the integrality of D_{k}, D_{k−1} implies that D_{k}^{new} ≤ D_{k−1}^{old} / 2 and thus D^{new} ≤ D^{old}/2.

2. This is an immediate consequence of (1) and the fact that the entity D remains a positive integer throughout the computation. □

Remarks. 1. Due to floating point errors the extended L^{3}F P performs more than \binom{m}{2} log_{1/δ} B many swaps b_{k−1} ↔ b_{k}. The number of swaps is about τ^{−1} log_{2} B times this bound.

2. A somewhat different entity D has been used in [23]. There we defined D′ = ∏_{i=1}^{m−1} D′_{i} with

D′_{i} = ∏_{{j=1 \atop b̂_{j} ≠0}}^{i} ∥b̂_{j}∥^{2}.

A detailed analysis shows that every exchange b_{k−1} ↔ b_{k} achieves

D^{′new} ≤ δ D^{′old} if b̂_{k−1}^{new} ≠ 0
D^{′new} ≤ D^{′old} if b̂_{k}^{new} = 0.

5 Block Korkin Zolotarev reduction

Let L = L(b_{1}, …, b_{m}) ⊂ IR^{n} be a lattice with ordered basis b_{1}, …, b_{m}. Let π_{i} : IR^{n} → span(b_{1}, …, b_{i−1})^{⊥} denote the orthogonal projection so that b − π_{i}(b) ∈ span(b_{1}, …, b_{i−1}). We let L_{i} denote the lattice π_{i}(L), which is a lattice of rank m − i + 1.

An ordered basis b_{1}, …, b_{m} of lattice L is a Korkin–Zolotarev basis if it is size–reduced and if

∥b̂_{i}∥ = λ_{1}(L_{i}) for i = 1, …, m.

This definition is equivalent to the one given, in the language of quadratic forms, by Hermite in his second letter to Jacobi (1845) and by Korkin and Zolotarev (1873).

Theorem 3 shows the strength of Korkin–Zolotarev reduction compared to L^{3}–reduction, see Theorem 1.

Theorem 3 [13] Every Korkin–Zolotarev basis b_{1}, …, b_{m} satisfies

\frac{4}{(i + 3)} ≤ ∥b_{i}∥^{2} / λ_{i}^{2} ≤ \frac{i + 3}{4} for i = 1, …, m.

The fastest known algorithm for Korkin–Zolotarev reduction of a basis b_{1}, …, b_{m} ∈ ZZ^{n} with B = max(∥b_{1}∥^{2}, …, ∥b_{m}∥^{2}) has a theoretic worst case time bound of \sqrt{n}^{n+o(n)} + O(n^{4} log B) arithmetic steps on O(n log B)–bit integers [23]. This algorithm is an improved version of Kannan’s shortest lattice vector algorithm [11].

Schnorr [23] introduced the following notion of a block Korkin–Zolotarev reduced basis. Let β be an integer, 2 ≤ β < m.

A lattice basis b_{1}, …, b_{m} is β–reduced if it is size–reduced and if

∥b̂_{i}∥ ≤ λ_{1}(L_{i}(b_{1}, …, b_{min(i+β−1,m)})) for i = 1, …, m − 1.

Let α_{β} denote the maximum of ∥b_{1}∥ / ∥b̂_{β}∥ taken over all Korkin–Zolotarev reduced basis b_{1}, …, b_{β}. We have α_{2} = \frac{4}{3}, α_{3} = \frac{3}{2} and α_{β} ≤ β^{1+ln β}, where ln β is the natural logarithm of β [23]. The constant α_{β}^{1/(β−1)} slowly converges to 1 as β increases. The corresponding constant α in Theorem 1 is at least 4/3. The strength of β–reduced bases compared to L^{3}–reduced bases can be seen from the following

Theorem 4 [23] Every β–reduced basis b_{1}, …, b_{m} of lattice L satisfies ∥b_{1}∥^{2} ≤ α_{β}^{(m−1)/(β−1)}λ_{1}(L)^{2} provided that β − 1 divides m − 1.

We call the basis b_{1}, …, b_{m} β–reduced with δ, 1/4 < δ ≤ 1, if it is size– reduced and if

δ ∥b̂_{i}∥^{2} ≤ λ_{1}(L_{i}(b_{1}, …, b_{min(i+β−1,m)}))^{2} for i = 1, …, m − 1.

Theorem 5 A basis b_{1}, …, b_{m} ∈ IR^{n} is 2–reduced with δ, 1/3 ≤ δ ≤ 1, if and only if it is L^{3}–reduced with δ.

Proof. “ ⇒ ” If b_{1}, …, b_{m} is 2–reduced with δ then we have

δ ∥b̂_{k}∥^{2} ≤ ∥π_{k}(v_{k}b_{k} + v_{k+1}b_{k+1})∥^{2}

for all (v_{k}, v_{k+1}) ∈ ZZ^{2}−0 and for k = 1, …, m−1. With v_{k} = 0, v_{k+1} = 1 this yields δ ∥b̂_{k}∥^{2} ≤ ∥π_{k}(b_{k+1})∥^{2}. “ ⇐ ” We show that the inequality

∥π_{k}(v_{k}b_{k} + v_{k+1}b_{k+1})∥^{2} = (v_{k} + μ_{k+1,k}v_{k+1})^{2} ∥b̂_{k}∥^{2} + |v_{k+1}|^{2}∥b̂_{k+1}∥^{2}
≥ δ ∥b̂_{k}∥^{2}

holds for all (v_{k}, v_{k+1}) ∈ ZZ^{2} − (0, 0). If v_{k+1} = 0 this inequality clearly holds. If v_{k+1} = ±1 the minimal value for |v_{k} + μ_{k+1,k}v_{k+1}| occurs at v_{k} = 0. This is because |μ_{k+1,k}| ≤ 1/2. From this and since the basis is L^{3}–reduced with δ we see that the desired lower bound ∥π_{k}(b_{k+1})∥^{2} ≥ δ ∥b̂_{k}∥^{2} holds. If |v_{k+1}| ≥ 2 the desired lower bound follows from

4 ∥b̂_{k+1}∥^{2} ≥ 4(δ − 1/4) ∥b̂_{k}∥^{2} ≥ δ ∥b̂_{k}∥^{2}.

Here we use that δ ≥ 1/3 and that the basis is L^{3}–reduced with δ. □

The first part of the above proof does not require that δ ≥ 1/3, thus any basis that is 2–reduced with δ is also L^{3}–reduced with δ.

6 A practical algorithm for block Korkin Zolotarev reduction

The following algorithm BKZ performs a β–reduction with δ. It uses L^{3}F P and a subroutine ENUM(j, k) defined below which minimizes the expression

c_{j}(u_{j}, …, u_{k}) := ∑_{s=j}^{k}(∑_{i=s}^{k} u_{i}μ_{i,s})^{2}c_{s}

for (u_{j}, …, u_{k}) ∈ ZZ^{k−j+1} − 0^{k−j+1}.

Algorithm BKZ for block Korkin–Zolotarev reduction INPUT b_{1}, …, b_{m} ∈ ZZ^{n}, δ with 1/2 < δ < 1, β with 2 < β < m.

1. L^{3}F P (b_{1}, …, b_{m}, δ), z := 0, j := 0

WHILE z < m − 1 DO j := j + 1, k := min(j + β − 1, m) IF j = m THEN [ j := 1, k := β ]

2. ENUM(j, k)

(this finds the minimal place (u_{j}, …, u_{k}) ∈ ZZ^{k−j+1} − 0^{k−j+1} and the minimal value c̄_{j} for c_{j}(u_{j}, …, u_{k}) and also b_{j}^{new} := ∑_{s=j}^{k} u_{s}b_{s}).

3. h := min(k + 1, m)

IF δc_{j} > c̄_{j}

THEN [ F_{c} := true, call L^{3}F P (b_{1}, …, b_{j−1}, b_{j}^{new}, b_{j}, …, b_{h}, δ)

at stage j, z := 0 ]

ELSE [ z := z + 1, call L^{3}F P (b_{1}, …, b_{h}, 0.99) at stage h − 1 ]

OUTPUT b_{1}, …, b_{m} (a basis that is β–reduced with δ).

COMMENTS. 1. Throughout the algorithm the integer j is cyclically shifted through the integers 1, 2, …, m − 1. The variable z counts the number of positions j that satisfy the inequality δ∥b̂_{j}∥^{2} ≤ λ_{1}(π_{j}(L(b_{j}, …, b_{k})))^{2}. If this inequality does not hold for j then we insert b_{j}^{new} into the basis, we call L^{3}F P and we reset z to 0. The integer j = m is skipped since the inequality always holds for j = m. Obviously a basis b_{1}, …, b_{m} is β–reduced with δ if it is size–reduced and z = m − 1. On termination the basis is size– reduced by the calls of L^{3}F P in Step 3 and we have z = m − 1. Therefore the algorithm produces, up to floating point errors, a basis that is β–reduced with δ.

2. The first call of L^{3}F P in Step 3 transforms the generator system b_{1}, …, b_{j−1}, b_{j}^{new}, b_{j}, …, b_{h} of lattice L(b_{1}, …, b_{h}) into a basis for L(b_{1}, …, b_{h}) that is L^{3}–reduced with δ. Alternatively we can extend b_{1}, …, b_{j−1}, b_{j}^{new} to a basis b_{1}, …, b_{j−1}, b_{j}^{new}, …, b_{h}^{new} of the lattice L(b_{1}, …, b_{h}) using the coefficients u_{i} in the representation b_{j}^{new} = ∑_{i=j}^{h} u_{i}b_{i}. For this we compute T ∈ GL_{h−j+1}(ZZ) with [u_{j}, …, u_{h}]T = [1, 0, …, 0] and we set [b_{j}^{new}, …, b_{h}^{new}] := [b_{j}, …, b_{h}]T^{−1}.

3. Setting F_{c} to true in Step 3 before inserting the new vector b_{j}^{new} into the basis means that the μ_{j,i} that are generated next on stage j will be corrected. This correction is necessary since some precision bits will be lost during the reduction in size of b_{j}^{new}.

4. The second call of L^{3}F P in Step 3 makes sure that the vectors b_{j}, …, b_{k} are always L^{3}–reduced with δ when calling ENUM(j, k).

5. We cannot prove that algorithm BKZ runs in polynomial time. However the algorithm behaves well in practice, see section 7.

Algorithm ENUM INPUT j, k with 1 ≤ j < k ≤ m (the following parameters of BKZ are used: b_{j}, …, b_{k}, c_{i} = ∥b̂′_{i}∥^{2} for i = j, …, k and μ_{i,t} for j ≤ t < i ≤ k)

1. c̄_{j} := c_{j}, ũ_{j} := u_{j} := 1, y_{j} := △_{j} := 0, s := t := j, δ_{j} := 1 FOR i = j +1, …, k+1 DO [c̃_{i} := u_{i} := ũ_{i} := y_{i} := △_{i} := 0, δ_{i} := 1]

2. WHILE t ≤ k DO c̃_{t} := c̃_{t+1} + (y_{t} + ũ_{t})^{2}c_{t}

IF c̃_{t} < c̄_{j}
THEN IF t > j

THEN [ t := t − 1, y_{t} := ∑_{i=t+1}^{s} ũ_{i}μ_{i,t},

ũ_{t} := v_{t} := ⌈−y_{t}⌋, △_{t} := 0
IF ũ_{t} > −y_{t} THEN δ_{t} := −1
ELSE δ_{t} := 1 ]

ELSE [c̄_{j} := c̃_{j}, u_{i} := ũ_{i} for i = j, …, k]

ELSE [ t := t + 1, s := max(s, t)

IF t < s THEN △_{t} := −△_{t}

IF △_{t}δ_{t} ≥ 0 THEN △_{t} := △_{t} + δ_{t} ũ_{t} := v_{t} + △_{t} ]

b_{j}^{new} := ∑_{i=j}^{k} u_{i}b_{i}

OUTPUT the minimal place (u_{j}, …, u_{k}) ∈ ZZ^{k−j+1} − 0^{k−j+1} and the minimum c̄_{j} of c_{j}(u_{j}, …, u_{k}) and b_{j}^{new}.

COMMENTS. 1. The algorithm ENUM enumerates in depth first search all integer vectors (ũ_{t}, …, ũ_{k}) for t = k, …, j that satisfy c_{t}(ũ_{t}, …, ũ_{k}) < c̄_{j} where c̄_{j} is the current minimum for the function c_{j}. The current minimal place is (u_{j}, …, u_{k}). We always have that c̃_{t} = c_{t}(ũ_{t}, …, ũ_{k}) for the current vector (ũ_{t}, …, ũ_{k}). Redundancies have been eliminated so that the following holds throughout the enumeration. The largest i with ũ_{i} ≠ 0 satisfies ũ_{i} > 0. This is because arriving at level t for the first time from level t − 1 we set △_{t} = 1 and ũ_{t} = 1.

2. Throughout the enumeration s is the maximal previous value for t.

3. When initially we arrive at level t from level t−1 we have y_{t} = △_{t} = 0 and s = t. Then we set △_{t} to 1 and ũ_{t} to 1. When subsequently level t is reached from level t − 1 we take for △_{t} the next value in order 1, −1, 2, −2, 3, −3, … as long as c̃_{t} ≥ c̄_{j}. At this latter point we increment t to t + 1 and s to s + 1. When level t is reached from level t + 1 we set △_{t} to 0 and we assign to δ_{t} the sign of −y_{t} +⌈−y_{t}⌉. When subsequently level t is reached from level t−1 we take for △_{t} the next value in either the order 1, −1, 2, −2, 3, −3 ⋯, or in the order −1, 1, −2, 2, −3, 3 ⋯, as long as c̃_{t} ≥ c_{j}. (The choice of the order depends on δ_{t} and it is made so that the values (y_{t} + ⌈−y_{t}⌋ + △_{t})^{2}c_{t} do not decrease for the chosen sequence △_{t}.) At this latter point t is incremented to t + 1.

4. Our original ENUM–algorithm, see [26], did not enumerate the values (y_{t}+⌈−y_{t}⌋+△_{t})c_{t} in increasing order. The new ENUM–algorithm is slightly better for block Korkin–Zolotarev reduction with pruning, see the end of section 7.

7 Solving subset sum problems

Given positive integers a_{1}, …, a_{n}, s we wish to solve the equation ∑_{i=1}^{n} a_{i}x_{i} = s with x_{1}, …, x_{n} ∈ {0, 1}. We associate to these integers the following basis b_{1}, …, b_{n+1} ∈ ZZ^{n+2}.

b_{1} = (2, 0, …, 0, na_{1}, 0)
b_{2} = (0, 2, …, 0, na_{2}, 0)
⋮  (1)
b_{n} = (0, 0, …, 2, na_{n}, 0)
b_{n+1} = (1, 1, …, 1, ns , 1).

Every lattice vector z = (z_{1}, …, z_{n+2}) ∈ L(b_{1}, …, b_{n+1}) that satisfies

|z_{n+2}| = 1, z_{n+1} = 0, z_{1}, …, z_{n} ∈ {±1}  (2)

yields the following solution for the subset sum problem

x_{i} = |z_{i} − z_{n+2}| / 2 for i = 1, …, n.  (3)

The following algorithm SUBSETSUM improves the Lagarias–Odlyzko algorithm [14] for solving low density subset sum problems in various ways. It uses the lattice basis (1) that is better suited than the Lagarias–Odlyzko basis. It has been proved rigorously that for almost all subset sum problems of density less than 0.9408 the shortest lattice vector yields a solution of the subset sum problem [3]. SUBSETSUM also uses superior algorithms for lattice basis reduction. Step 5 of the algorithm has already been used in [22].

Algorithm SUBSETSUM INPUT a_{1}, …, a_{n}, s ∈ IN

1. Compute the basis (1), let b_{i} = (b_{i,1}, …, b_{i,n+2}) for i = 1, …, n + 1.

2. Randomly permute b_{1}, …, b_{n+1} so that the permuted basis starts with the vectors b_{i} satisfying b_{i,n+2} ≠ 0.

3. Reduce the basis b_{1}, …, b_{n+1}, using modifications of L^{3}F P (b_{1}, …, b_{n+1}, 0.99) or BKZ(b_{1}, …, b_{n+1}, 0.99, β)

4. IF some vector (z_{1}, …, z_{n+2}) in the reduced basis satisfies (2) THEN [OUTPUT x_{i} = |z_{i} − z_{n+2}| / 2 for i = 1, …, n and stop ]

5. (reduce pairs of basis vectors)

Sort b_{1}, …, b_{n+1} so that ∥b_{1}∥ ≤ ∥b_{2}∥ ≤ ⋯ ≤ ∥b_{n+1}∥

FOR j = 1, …, n FOR k = 1, …, j − 1 DO

IF ∥b_{j} ± b_{k}∥ < ∥b_{j}∥ THEN [ b_{j} := b_{j} ± b_{k}, F := true ]

IF F THEN [F := false, GOTO 5].

REPEAT steps 2 – 5 15–times.

M. Euchner has evaluated this algorithm as part of his master thesis. He used the following reduction subroutines in Step 3:

1) L^{3}F P (b_{1}, …, b_{n+1}, 0.99),

2) L^{3}F P (b_{1}, …, b_{n+1}, 0.99) with deep insertions,

3) BKZ(b_{1}, …, b_{n+1}, 0.99, 10),

4) BKZ(b_{1}, …, b_{n+1}, 0.99, 20).

In order to optimize the program M. Euchner has added the following features. He checks after each size–reduction whether the reduced vector b_{k} satisfies (2) and yields a solution. He incorporates the deep insertion rule

(b_{1}, …, b_{k}) := (b_{1}, …, b_{i−1}, b_{k}, b_{i}, …, b_{k−1})

for indices i ≤ 5 and arbitrary k. He assumes that ∑_{i=1}^{n} x_{i} = n/2 holds for the solution (x_{1}, …, x_{n}) and therefore extends the vectors b_{i} in (1) by adding the component b_{i,n+3} = n for i = 1, …, n and b_{n+1,n+3} = n^{2}/2.

Statistical evaluation of the algorithm Every row with first entries n, b in the following statistic corresponds to 20 random inputs for SUB-SETSUM that are generated as follows. Pick random numbers a_{1}, …, a_{n} in the interval [1, 2^{b}], pick a random subset I ⊂ {1, …, n} of size n/2, put s = ∑_{i∈I} a_{i}. The numbers in columns suc_{1}, #suc are the number of successes in round 0 of steps 2 – 5 and the total number of successes in all rounds for these 20 inputs. The number in column # rou gives the total number of rounds of steps 2 – 5 for the 20 inputs. There is a minimum of 20 and a maximum of 16 · 20 = 320 rounds. The column hh : mm : ss gives the average CPU–time per problem on a UNISYS 6000/70. The times marked with * are on a SPARC 1+. On a SPARC 1+ computer our programs are about 6 times faster.

L^{3}F P, δ = 0.99  L^{3}F P, δ = 0.99, with deep insertions
n b suc_{1} #suc #rou hh:mm:ss suc_{1} #suc #rou  hh:mm:ss
42 24  20  20  20  0:39  20  20  20  0:51
42 28  13  20  33  1:22  17  20  25  1:59
42 32  2  19  65  3:05  14  20  51  4:00
42 36  2  20  98  4:49  13  19  52  4:42
42 40  4  17 124  6:11  17  19  47  4:18
42 44  7  20  65  3:50  17  20  27  3:23
42 48  10  20  42  2:51  19  20  21  2:50
42 52  17  20  23  1:56  20  20  20  2:34
42 56  19  20  22  1:59  20  20  20  2:31
42 60  19  20  21  1:56  20  20  20  2:39
50 26  16  20  25  1:23  20  20  20  1:42
50 30  7  20  45  3:10  17  20  24  4:07
50 34  4  20  79  6:11  10  20  39  7:25
50 38  1  17 126  10:17  8  19  68  14:43
50 42  0  10 258  22:16  11  19  68  14:50
50 46  0  6 265  23:37  8  17  91  20:53
50 50  0  12 212  19:32  5  19  72  20:11
50 54  1  15 172  16:26  13  20  34  12:17
50 58  4  17 139  14:17  18  20  22  8:57
50 62  5  20  72  8:20  19  20  21  7:13
50 66  12  20  33  5:07  20  20  20  7:00
50 70  15  20  31  4:58  20  20  20  6:09
58 29  11  20  35  3:39  18  20  22  4:03
58 35  3  20 103  13:05  13  20  48  16:37
58 41  1  15 218  30:00  4  16 120  42:34
58 47  0  3 296  42:02  1  17 117  58:15
58 53  0  1 315  46:37  3  10 218  1:47:04
58 58  0  2 309  48:38  1  12 198  1:55:35
58 63  1  6 275  44:26  7  20  83  1:04:08
58 69  2  12 204  34:18  15  20  34  32:25
58 75  1  16 122  23:13  15  20  28  27:08
58 81  3  20  79  17:09  19  20  21  16:52
58 87  11  20  42  11:40  20  20  20  12:36
58 93  13  20  30  10:22  20  20  20  15:16

L^{3}F P, δ = 0.99  L^{3}F P, δ = 0.99 with deep insertions
n  b suc_{1} # suc # rou hh:mm:ss suc_{1} # suc # rou  hh:mm:ss
66 18  20  20  20  1:11  20  20  20  1:34
66 26  19  20  21  2:03  20  20  20  2:58
66 34  5  20  50  9:05  12  20  33  15:53
66 42  1  16  210  44:01  3  19  124  1:10:43
66 50  0  0  320  10:14*  0  8  250  2:43:16
66 58  0  1  319  14:05*  0  4  291  4:55:39
66 66  0  0  320  11:03*  0  9  237  5:16:29
66 72  0  0  320  11:36*  1  19  125  3:45:28
66 80  0  2  315  1:23:50  9  20  69  2:35:15
66 88  1  13  203  58:18  10  20  46  2:15:07
66 96  0  16  173  51:44  17  20  23  57:32
66 104  3  17  144  46:17  20  20  20  25:51
66 112  11  20  39  20:29  20  20  20  33:36

BKZ, δ = 0.99, β = 10  BKZ, δ = 0.99, β = 20
n b suc_{1} #suc #rou hh:mm:ss suc_{1} #suc #rou hh:mm:ss
42 24  20  20  20  0:40  20  20  20  0:40
42 28  20  20  20  1:49  18  20  22  2:28
42 32  17  20  39  4:52  20  20  20  2:58
42 36  11  18  59  8:53  15  19  45  7:27
42 40  15  20  31  5:50  18  20  30  7:05
42 44  14  20  41  8:02  19  20  25  4:46
42 48  19  20  21  2:38  20  20  20  2:40
42 52  20  20  20  2:07  20  20  20  2:19
42 56  20  20  20  2:02  20  20  20  2:05
42 60  20  20  20  2:03  20  20  20  2:07
50 26  19  20  21  2:30  20  20  20  2:11
50 30  19  20  22  3:32  20  20  20  4:25
50 34  15  20  26  7:55  18  20  22  7:54
50 38  4  19  73  19:20  17  20  25  15:24
50 42  8  19  74  25:22  14  19  53  30:51
50 46  4  11 200  58:33  10  20  77  48:15
50 50  8  20  48  25:09  16  19  41  26:28
50 54  14  20  46  18:04  19  20  22  16:57
50 58  17  20  26  10:48  20  20  20  12:28
50 62  19  20  23  9:10  20  20  20  8:45
50 66  20  20  20  7:12  20  20  20  7:11
50 70  20  20  20  6:19  20  20  20  5:53
58 29  19  20  21  4:23  20  20  20  5:45
58 35  16  20  25  9:35  17  20  26  18:38
58 41  3  18 111  50:58  10  20  34  48:20
58 47  0  14 213  1:38:43  10  17  89  16:31^{∗}
58 53  0  8 242  2:06:24  6  15 130  31:49^{∗}
58 58  9  16 105  2:10:52  2  16 155  3:45:43
58 63  11  19  68  1:44:42  15  20  35  1:14:38
58 69  16  20  27  49:25  19  20  21  42:52
58 75  20  20  20  19:57  20  20  20  28:39
58 81  19  20  21  23:02  20  20  20  16:55
58 87  20  20  20  12:52  20  20  20  12:05
58 93  20  20  20  15:40  20  20  20  11:30

BKZ, δ = 0.99, β = 10  BKZ, δ = 0.99, β = 20
n  b suc_{1} # suc # rou hh:mm:ss suc_{1} # suc # rou hh:mm:ss
66 18  20  20  20  0:12*  20  20  20  0:12*
66 26  20  20  20  0:31*  20  20  20  0:33*
66 34  16  20  25  1:55*  20  20  20  1:59*
66 42  2  17  92  8:32*  9  20  49  12:43*
66 50  1  6  269  24:07*  2  13  215  56:50*
66 58  0  1  310  30:05*  2  10  203 1:25:14*
66 66  0  0  320  35:43*  2  8  236 1:45:11*
66 72  3  10  209  27:40*  3  16  155 1:34:07*
66 80  10  20  69  4:55:40  17  20  39  5:37:05
66 88  13  20  42  3:13:48  18  20  22  1:13:37
66 96  19  20  21  1:39:04  20  20  20  54:01
66 104  20  20  20  26:30  20  20  20  31:54
66 112  20  20  20  34:26  20  20  20  26:45

The above statistic shows that L^{3}F P –reduction with deep insertions is much stronger than straight L^{3}F P –reduction. It is even stronger than BKZ–reduction with block size 10 and nearly matches the performance of BKZ–reduction with block size 20. The success rates of BKZ–reduction improves greatly with increasing block size but the running time increases as well.

Comparison with La Macchia’s results. La Macchia [15] also used the lattice basis (1) to solve subset sum problems. La Macchia minimizes floating point errors in the L^{3}–reduction by using initially Seysen’s reduction algorithm. A comparison of La Macchia’s and our success rates has to take into account that La Macchia applies 5 independent randomizations to the initial basis which increases the success rates by a factor between 1 and 5. La Macchia’s success rates for a single randomization of the initial basis are consistently lower than ours for L^{3}F P. Our improved success rates are due to the deep insertion rule that is used for indices i ≤ 5.

Block Korkin Zolotarev reduction with pruning. We can speed up BKZ–reduction with large block size by pruning the enumeration tree that is produced by the procedure ENUM. For example we set α_{t} := min \{1.05 \frac{k−t+1}{k−j}, 1\} and we replace in Step 2 of ENUM the predicate “IF c̃_{t} < c̄_{j}” by “IF c̃_{t} < α_{t}c̄_{j}”. Note that α_{t} is rather small if t is close to k and which is near 1 if t is close to j. Here are some performance data for solving subset sum problems using this pruned variant of block Korkine Zolotarev reduction. This algorithm improves the success rates of BKZ–reduction with block size 20 as is shown by the first block of the table. For dimension 106 we have reduced the number of problems per row. This number is given in the last column.

BKZ, δ = 0.99, β = 50, α_{t} = min (1.05 \frac{k−t+1}{k−j}, 1)
n  b suc_{1} # suc # rou hh : mm : ss # problems per row
66 26  20  20  20  0:36*  20
66 34  20  20  20  3:54*  20
66 42  20  20  20  15:55*  20
66 50  10  19  78  1:30:19*  20
66 58  9  14  119  3:40:26*  20
66 66  10  19  70  3:05:43*  20
66 72  18  20  26  1:18:22*  20
66 80  20  20  20  38:10*  20
66 88  20  20  20  36:09*  20
66 96  20  20  20  28:40*  20
72 106  20  20  20  1:11:34*  20
72 118  20  20  20  1:19:14*  20
72 130  20  20  20  1:02:20*  20
82 134  20  20  20  1:25:20*  20
82 146  20  20  20  1:34:46*  20
82 158  20  20  20  1:23:02*  20
106 180  5  5  5  19:15:55*  5
106 210  10  10  10  7:30:27*  10
106 240  10  10  10  3:14:50*  10
106 270  10  10  10  2:49:52*  10
106 300  10  10  10  3:53:18*  10

Acknowledgement The first author likes to thank the students of his class in summer 1990 for evaluating early versions of the present algorithms for lattice basis reduction and for evaluating early versions of the lattice basis (1). He also wishes to thank SIEMENS/NIXDORF and the Frankfurt department of Computer Science for their support.

References

[1] E.F. Brickell: Solving low density knapsacks. Advances in Cryptology, Proceedings of CRYPTO’83, Plenum Press, New York (1984), 25–37.

[2] B. Chor and R. Rivest: A knapsack–type public key cryptosystem based on arithmetic in finite fields. IEEE Trans. Information Theory IT–34 (1988), 901–909.

[3] M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.P. Schnorr and J. Stern: An improved low–density subset sum algorithm. computational complexity 2, (1992), 97–186.

[4] P. van Emde Boas: Another NP–complete partition problem and the complexity of computing short vectors in a lattice. Rept. 81–04, Dept. of Mathematics, Univ. of Amsterdam, 1981.

[5] M. Euchner: Praktische Algorithmen zur Gitterreduktion und Faktorisierung. Diplomarbeit Uni. Frankfurt (1991).

[6] A. M. Frieze: On the Lagarias–Odlyzko algorithm for the subset sum problem. SIAM J. Comput. 15 (2) (1986), 536–539.

[7] M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP–Completeness. W. H. Freeman and Company (1979).

[8] J. Hastad, B. Just, J. C. Lagarias and C. P. Schnorr: Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput. 18 (5) (October 1989), 859–881.

[9] C. Hermite: Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objects de la théorie des nombres. Deuxième lettre du 6 août 1845. J. Reine Angew. Math. 40 (1850), 279–290.

[10] A. Joux and J. Stern: Improving the critical density of the Lagarias– Odlyzko attack against subset sum problems. Proceedings of Fundamentals of Computation Theory, FCT’91, Ed. L. Budach, Springer LNCS 529 (1991), pp. 258–264.

[11] R. Kannan: Minkowski’s Convex Body Theory and Integer Programming. Math. Oper. Res. 12 (1987), 415–440.

[12] A. Korkine and G. Zolotareff: Sur les formes quadratiques. Math. Ann. 6 (1873), 366–389.

[13] J.C. Lagarias, H.W. Lenstra, Jr. and C.P. Schnorr: Korkin– Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice. Combinatorica 10 (1990), pp. 333–348.

[14] J. C. Lagarias and A. M. Odlyzko: Solving low–density subset sum problems. J. Assoc. Comp. Mach. 32(1) (1985), 229–246.

[15] B. A. LaMacchia: Basis Reduction Algorithms and Subset Sum Problems. SM Thesis, Dept. of Elect. Eng. and Comp. Sci., Massachusetts Institute of Technology, Cambridge, MA (1991). In preparation.

[16] H. W. Lenstra, Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8 (1983), pp. 538–548.

[17] A.K. Lenstra, H.W. Lenstra, and L. Lovász: Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515–534.

[18] L. Lovász: An algorithmic theory of numbers, graphs and convexity. SIAM Publications, Philadelphia (1986).

[19] L. Lovász and H. Scarf: The generalized basis reduction algorithm. Math. Oper. Res. (1992).

[20] A. M. Odlyzko: The rise and fall of knapsack cryptosystems. Cryptology and Computational Number Theory, C. Pomerance, ed., Am. Math. Soc., Proc. Symp. Appl. Math. 42 (1990), 75–88.

[21] A. Paz and C. P. Schnorr: Approximating integer lattices by lattices with cyclic factor groups. Automata, Languages, and Programming: 14th ICALP, Lecture Notes in Computer Science 267, Springer–Verlag, NY (1987), 386–393.

[22] S. Radziszowski and D. Kreher: Solving subset sum problems with the L^{3} algorithm. J. Combin. Math. Combin. Comput. 3 (1988), 49–63.

[23] C. P. Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science 53 (1987), 201–224.

[24] C. P. Schnorr: A more efficient algorithm for lattice basis reduction. J. Algorithms 9 (1988), 47–62.

[25] C. P. Schnorr: Factoring integers and computing discrete logarithms via diophantine approximation. Proceedings EUROCRYPT’91, Brighton, May 1991, Springer LNCS 547 (1991), pp. 281–293.

[26] C. P. Schnorr and M. Euchner: Lattice basis reduction: improved algorithms and solving subset sum problems. Proceedings of Fundamentals of Computation Theory, FCT’91, Ed. L. Budach, Springer LNCS 529, (1991), pp. 68–85.

[27] M. Seysen: Simultaneous reduction of a lattice basis and its reciprocal basis. To appear in Combinatorica.