The subset sum problem

The difficulty of the subset sum problem was the basis for the (presumed) security of the first public-key encryption scheme, called the Merkle-Helhnan knapsack scheme (§8.6.1).

3.90 Definition The subset sum problem (SUBSET-SUM) is the following: givenaset{ai,a2, ... ,an} of positive integers, called a knapsack set, and a positive integer s, determine whether or not there is a subset of the a3 that sum to s. Equivalently, determine whether or not there exist Xi € {0.1}, 1 < i < n, such that ^Г=1 а<Хг = s-

The subset sum problem above is stated as a decision problem. It can be shown that the problem is computationally equivalent to its computational version which is to actually determine the x, such that aXi = s> provided that such x, exist. Fact 3.91 provides evidence of the intractability of the subset sum problem.

3.91 Fact The subset sum problem is NP-complete. The computational version of the subset sum problem is NP-hard (see Example 2.74).

Algorithms 3.92 and 3.94 give two methods for solving the computational version of the subset sum problem; both are exponential-time algorithms. Algorithm 3.94 is the fastest method known for the general subset sum problem.

3.92 Algorithm Naive algorithm for subset sum problem

INPUT: a set of positive integers {ai, аг,... , an} and a positive integer s. OUTPUT: Xi € {0.1}, 1 < i < n, such that £]Г=1 а*х« = provided such xt exist.

  • 1. For each possible vector (xi, хг,... , xn) € 2)" do the following:
  • 1.1 Compute l = X]"=r а«ж*-
  • 1.2 If / = s then retum(a solution is (xi, X2,... , xn)).
  • 2. Retum(no solution exists).
  • 3.93 Fact Algorithm 3.92 takes 0(2") steps and, hence, is inefficient.

3.94 Algorithm Meet-in-the-middle algorithm for subset sum problem

INPUT: a set of positive integers {ai, a2,... , an} and a positive integer s.

OUTPUT: Xi € {0.1}, 1 < i < n, such that ^”=i (4'xi = provided such exist.

  • 1. Set t<—[n/2.
  • 2. Construct a table with entries (^*=i o-iXi, (xi, x2,... , xt)) for (xi, x2,... ,xt) € (Z2)*. Sort this table by first component.
  • 3. For each (xt+i,xt+2,... ,xn) e (Z2)n_t, do the following:
  • 3.1 Compute l = s - Xw=t+i a>x> ancl check, using a binary search, whether l is the first component of some entry hi the table.
  • 3.2 If/ = Xa=i aixi then retumfa solution is (xi,x2,... ,xn)).
  • 4. Retumfno solution exists).
  • 3.95 Fact Algorithm 3.94 takes 0(n2"/2) steps and, hence, is inefficient.
  • 3.10.1 The L3-lattice basis reduction algorithm

The L3-lattice basis reduction algorithm is a crucial component in many number-theoretic algorithms. It is useful for solving certain subset sum problems, and has been used for cryptanalyzing public-key encryption schemes which are based on the subset sum problem.

3.96 Definition beta; = {x,x2,... ,x„) and у = (yi, y2,.. ■ , yn) be two vectors in R". The inner product of x and у is the real number

3.97 Definition Let у = (yi, y2,. ■ ■ . yn) be a vector in R”. The length of у is the real number

3.98 Definition Let В = {bi,b2, . . , bm} be a set of linearly independent vectors in R" (so that m < n). Tlie set L of all integer linear combinations of bi, 62, • • ■ , bm is called a lattice of dimension m; that is, L = Zbi + Zb2 + • • • + Zb,n. The set В is called a basis for the lattice L.

A lattice can have many different bases. A basis consisting of vectors of relatively small lengths is called reduced. The following definition provides a useful notion of a reduced basis, and is based on the Gram-Schmidt orthogonalization process.

3.99 Definition Let В = {bi,b2,, b„} be a basis for a lattice L c M'!. Define the vectors b* (1 < i < 7i) and the real numbers (1 < j < i < n) inductively by

The basis В is said to be reduced (more precisely, Lovasz-reduced) if

(where fiij denotes the absolute value of I4j), and

Fact 3.100 explains the sense in which the vectors in a reduced basis are relatively short.

  • 3.100 Fact Let L c Rn be a lattice with a reduced basis {61,62, •• • , 6„}-
  • (i) For every non-zero x 6 L, ||6i|| < 2^n_1^2||a;||.
  • (ii) More generally, for any set {«1, «2, • • • , at} of linearly independent vectors in L,

The L3-lattice basis reduction algorithm (Algorithm 3.101) is a polynomial-time algorithm (Fact 3.103) for finding a reduced basis, given a basis for a lattice.

3.101 Algorithm L3-lattice basis reduction algorithm

INPUT: a basis (61,62,.... 6„) for a lattice L in ]Rm, m > n.

OUTPUT: a reduced basis for L.

  • 1. 6{ bi, Bi— < 6{, 6{ >.
  • 2. For i from 2 to n do the following:
  • 2.1 6* ч—6,.
  • 2.2 For j from 1 to i - 1, set < 6,, 6* >jBj and 6*<—6* - mjb*.
  • 2.3 Bi<- < b*,b* >.
  • 3. ki—2.
  • 4. Execute subroutine RED(/,:,A- - 1) to possibly update some )i,j.
  • 5. If Bk < (| — nl k_1)Bk~ then do the following:
  • 5.1 Set B^Bk+ii2Bk~ 1, fj.k,k-i<—t*Bk-i/B, Bk^Bk-iBk/B,

and Bk-i^B.

  • 5.2 Exchange 6;. and 6fc_,.
  • 5.3 If к > 2 then exchange fikj and for j = 1,2,... , к 2.
  • 5.4 For i = к + 1, к + 2,... ,n:

Sett<-Щ'к, — nt, and щ:к-1^t +

  • 5.5 k<— max(2, к — 1).
  • 5.6 Go to step 4.

Otherwise, for / = к - 2, к - 3,... .1, execute RED(/.-,0, and finally set k^k + 1.

6. If к < n then go to step 4. Otherwise, retum(6i, 62,... , 6n).

RED(/;,/) If Ifik,i > 3 then do the following:

  • 1. 7‘i [0.5 + Hk.i, bk<—bk - rbi.
  • 2. For j from 1 to / - 1, set ^k,j<~^k,j ~
  • 3. - r.
  • 3.102 Note (explanation of selected steps of Algorithm 3.101)
  • (i) Steps 1 and 2 initialize the algorithm by computing 6* (1 < i < n) and (1 < j < i as defined in equations (3.9) and (3.8), and also B, =< b*, 6* > (1 < i < n).
  • (ii) к is a variable such that the vectors 61,62,... , bk-i are reduced (initially к = 2 in step 3). The algorithm then attempts to modify 6;., so that 61,62,... , 6/. are reduced.

(iii) In step 4, the vector bk is modified appropriately so that |/xfc,fc_i | < and the m-j are updated for 1 < j < к - 1.

(iv) In step 5, if the condition of inequality (3.10) is violated for i = k, then vectors brand br_! are exchanged and their corresponding parameters are updated. Also, к is decremented by 1 since then it is only guaranteed that b, bz,... , bk-2 are reduced. Otherwise, bk is modified appropriately so that k,j < 5 for j = 1,2,... , к — 2, while keeping (3.10) satisfied, к is then incremented because now bi, b2, • • •, br are reduced.

It can be proven that the L3-algorithm terminates after a finite number of iterations. Note that if L is an integer lattice, i.e. L c Z", then the L3-algorithm only operates on rational numbers. The precise running time is given next.

3.103 Fact Let L c Z" be a lattice with basis {bi, Ьг,... , b„}, and let C e R, C > 2, be such that ||bj||2 < C for ■i = 1,2,... , n. Then the number of arithmetic operations needed by Algorithm 3.101 is 0(n4 log C), on integers of size 0(n log C) bits.

 
Source
< Prev   CONTENTS   Source   Next >