# 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, ... ,a_{n}} of positive integers, called a *knapsack set,* and a positive integer s, determine whether or not there is a subset of the *a _{3}* 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 * ^{a}‘^{Xi}* = 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, аг,... , a_{n}} and a positive integer *s. *OUTPUT: *Xi* € {0.1}, 1 < *i <* n, such that £]Г=1 ^{а}*^{х}« ^{=} provided such *x _{t}* exist.

- 1. For each possible vector (xi, хг,... , x
_{n}) €*№**2**)"*do the following: - 1.1 Compute
*l =*X]"=r^{а}«^{ж}*- - 1.2 If / = s then retum(a solution is (xi, X2,... , x
_{n})). - 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, a_{2},... , a_{n}} and a positive integer *s.*

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

- 1. Set
*t<—[n/2.* - 2. Construct a table with entries (^*=i
*o-iXi*, (xi, x_{2},... ,*x*for (xi, x_{t}))€ (Z_{2},... ,x_{t})_{2})*. Sort this table by first component. - 3. For each
*(x*_{t+}i,x_{t+}*2**,... ,x*(Z_{n}) e_{2})^{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
then retumfa solution is (xi,x^{a}i^{x}i_{2},...*,x*_{n})). - 4. Retumfno solution exists).
- 3.95 Fact Algorithm 3.94 takes 0(n2"/
^{2}) steps and, hence, is inefficient. - 3.10.1
**The L**^{3}-lattice basis reduction algorithm

The L^{3}-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,x _{2},...* ,x„) and

*у = (yi, y*be two vectors in R". The

_{2},.. ■ , y_{n})*inner product*of

*x*and

*у*is the real number

3.97 Definition Let *у **= **(yi, y**2**,**. ■ ■* . *y _{n})* be a vector in R”. The

*length of*

*у*is the real number

3.98 Definition Let *В = {bi,b _{2},* . .

*■*,

*b*be a set of linearly independent vectors in R" (so that m < n). Tlie set

_{m}}*L*of all integer linear combinations of

*bi*

*,*6

_{2}, • • ■ ,

*b*is called a

_{m}*lattice*of

*dimension*m; that is,

*L = Zbi + Zb*+ • • • + Z

_{2}*b,*The set

_{n}.*В*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,b _{2},, 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 *I**4**j),* and

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

- 3.100 Fact Let
*L*c R^{n}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, • • • ,
*a*_{t}} of linearly independent vectors in*L,*

The L^{3}-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 L^{3}-lattice basis reduction algorithm

INPUT: a basis (61,62,.... 6„) for a lattice *L* in ]R^{m}, *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*then do the following:_{k}__{1})Bk~ - 5.1 Set
*B^Bk+ii*1,^{2}Bk~*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,... , 6_{n}).

RED(/;,/) If I*fik,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,6_{2},... ,*bk-i*are reduced (initially*к = 2*in step 3). The algorithm then attempts to modify 6;., so that 61,6_{2},... , 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,* b_{2}, • • •, br are reduced.

It can be proven that the L^{3}-algorithm terminates after a finite number of iterations. Note that if *L* is an integer lattice, i.e. *L* c Z", then the L^{3}-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(n^{4} log *C),* on integers of size *0(n* log *C)* bits.