It is not necessary to provide an efficient algorithm guaranteed to crack all instances of a cryptosystem to call its security into question, and our analysis is only an indication that the simple system of the previous section can often be broken.
Suppose we are given the sequence :
must be larger than all the , hence it must be significantly larger than the earliest members of the sequence.
The decryption method begins by guessing which of the known correspond to a few of the early members of the sequence. A trial-and-error approach is considered feasible for practical size problems.
Suppose we have guessed that 2464, 611, and 2456 correspond to the first three , and further that 2464 corresponds to .
It is plausible that restrictions of this kind give a lot of information about . As we look at all possible values of , mod 2464 is evenly distributed through the entire range from 0 to 2463. If we require, for example, that the number is either or , we would expect that only about of the values for satisfy this. It seems plausible that the distribution of is independent of the distribution of , so a similar restriction on the second number reduces the possible values of by .
In our example, implies and . We look at the values of for something which makes mod 2464 small. Part of the results:
[The published algorithm recommends guessing more than 3 of the lowest and determining from an integer program:
Since implies is close to , we try using , on the , which gives:
The were generated using , , . Comparison of the with the ``almost'' super-increasing sequence obtained above shows that, except for the first few terms, the ratio of terms from the two sequences is nearly constant. Since a multiple of a super-increasing sequence is super-increasing, this explains why we would expect to obtain a useful sequence.