1400 clearly cannot be in the set. If 650 is not in the set, we would be in trouble, since the sum of the remaining numbers is , hence . Thus 650 must be in the set, and we now have the task of finding numbers which add up to . 300 is too big, and the same reasoning as before shows that 150 must be in the set. If we continue, it is easy to identify the desired set as .
We began section 4.1 with the problem of identifying a subset of
To find the subset, begin by solving , which gives . If we let be the numbers in the easy problem, the hard problem can be written as
This would seem to give us a good public-key system: a problem which is easy once some special information (the 2039 and the 1000) is known, difficult without the information. Unfortunately, the special type of subset-sum problem created in this way can be solved even without the special information. There is a sequence of papers showing how to solve special subset-sum problems and proposing a refinement which, in turn, was solved by the next paper in the sequence. This has not happened with the RSA system, but there is no guarantee that it won't!