Breaking the

knapsack algorithm involves finding the values

`k` and

`m` such that

`m`*

`a`((

`i`) (mod

`k`) forms a superincreasing set (

`s`(

`i`)), where

`a`(

`i`) is the public set of weights. In the

graph `y` =

`m*a`1(mod

`k`),

`a`(

`i`) is the

slope of the function, and

discontinuities fall on the values:

`m` = ( (

`k`/

`a`(1)), (2

`k`/

`a`(1)) ... ((

`a`(1)-1)

`k`/

`a`(1))).

`m`*

`a`(1) (mod

`k`) or

`y` is less than 2

^{(-n+1)*k}, where

`n` is the number of weights in the

knapsack, because each

element in the superincreasing sack must be at least twice the previous. Therefore,

`m` must fall on the

interval ((

`pk`/

`a`(1)), (

`pk`/

`a`(1) + (2

^{(-n+1)k}/

`a`(1))).
where

`p` equals {1 .. (

`a`(1) -1)}. Dividing the set by

`k` leads to the ratio

`m/k` falling on the interval ((

`p`/

`a`(1)),((

`p`/

`a`(1)) + (1/(

`a`(1)*2

^{(n-1)})))
meaning the ratio falls on on of the intervals defined by the discontinuities on the graph

`y`=

`m`*

`a`(1) (mod

`k`).

This

procedure works with the second weight

`a`(2), where the ratio

`m/k` can have the values on the interval ((

`q`/

`a`(2)),((

`q`/

`a`(2)) + (1/(

`a`(2)*2

^{(n-2)})))
where

`q` = {1...

`a`(2)-1}. Both the first and second intervals must contain

`m/k`, and therefore the possible interval on which

`m/k` may fall is limited to the

intersection of the above mentioned.

Increasing the number of weights decreases further the interval, and thus with as few as 4 weights (

`m,k`) may be determined by

trial and error.

Sources: Applied Cryptography by Bruce Schneier