The Knapsack Scheme ( Merkle and Hellman, 1978) Given X=(XI, x2, . xn)and an integer S Finding B=(b,b,,, bn)where b ;=0or such that s=<X,B>=∑b;x NP-Complete in general5 The Knapsack Scheme (Merkle and Hellman, 1978) • Given X = (x1 , x2 ,…, xn ) and an integer s • Finding B = (b1 , b2 ,…, bn ) where bi = 0 or 1 such that s = < X, B> =  bi xi • NP-Complete in general