Super-Increasing Sequence X=(XI, x2,,n)is super-increasing if ∑ (2, 3, 6, 13, 27, 52)is super-increasing
6 Super-Increasing Sequence • X = (x1 , x2 ,…, xn ) is super-increasing if − = 1 1 i j i j x x • (2,3,6,13,27,52 ) is super-increasing
Greedy method Solve X=(2,36,13,27,52)ands=70 s>52? Yes zb1.s1=70-52=18 18>27?No=>b;=0 ·18>13?Yes=>bA=1.s2=18-13=5 5>6?No=>b2=0 5>3?Yes=>b2=1,S2=5-3=2 B=(12120,1,0,1)
7 Greedy Method • Solve X = (2,3,6,13,27,52 ) and s = 70 • s > 52? Yes ==> b6 = 1, s1 = 70 - 52 = 18 • 18 > 27? No ==> b5 = 0 • 18 > 13? Yes ==> b4 = 1, s2 = 18 - 13 = 5 • 5 > 6? No ==> b3 = 0 • 5> 3? Yes ==> b2 = 1, s2 = 5 - 3 = 2 • b1= 1 • B = (1,1,0,1,0,1)
Greedy method To solve for i=l down to 1 Ifs≥x s=s-X.b.=1 ·Els
8 Greedy Method • To solve: – for i =1 down to 1 • If sxi – s = s-xi , bi = 1 • Else – bi = 0
Knapsack Based Public-Key Key generation Choose a super-increasing sequence ⅹ=( Choose randomly two numbers y and such that GCD(N,Y)=l, and Y>>x
9 Knapsack Based Public-Key • Key Generation: – Choose a super-increasing sequence X = (x1 , x2 ,…, xn ) – Choose randomly two numbers Y and such that GCD(N,Y) = 1, and = n j j Y x 1
Knapsack Based Public-Key Public Key: K=(kI, k,.,kn)where k; =X, n modY Private Keys XN.Y
10 Knapsack Based Public-Key • Public Key: – K = (k1 , k2 ,…, kn ) where ki = xi N mod Y • Private Key: – X, N, Y