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*a1(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