Introduction to Cryptography with Open-Source Software

Public-key cryptosystems based on logarithms and knapsacks 129

(a

1

, a

2

, . . . , a

n

) and an integer N, is there a subset J of the list such that the

sum of the elements o f J is e qual to N ? For e xample, given the sequence

(14, 28, 56, 82, 90, 132, 197, 284, 341, 455)

can the number 516 be expressed as a sum of a subset of those values? (No,

it can’t.) However, 515 can be expressed as a sum of a subset (in three ways):

515 = 14 + 28 + 13 2 + 341

= 28 + 56 + 90 + 341

= 14 + 82 + 90 + 132 + 197.

This problem, the subset sum problem, is known to be a very hard problem;

in general there is no better way of determining whether or not we can have a

subset sum than by trial and error. For very la rge se quences (several hundred

elements), this approach becomes ...