# Algorithm to create a superincreasing sequence

I am building an implementation of the [Merkle-Hellman Knapsack Cryptosystem] for my study.(https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem)

One of the things I would like to do, is to create a new private key. A private key in the Knapsack Cryptosystem consists mostly* of a so-called superincreasing knapsack. This is a sequence of numbers K where `K[n] > (K[0] + K[1] + ... + K[n-1]`.

I am wondering if there are smart methods to construct a new sequence for which this holds true. It is easy to create a superincreasing knapsack (such as `1, 2, 4, 8, 16, ...`), but I've found it relatively hard until now to do this properly for a sequence that is not predictable.

Are there any algorithms (that probably incorporate a value from a random number generator in there) that can do this?

*there are also two more numbers to compute for the private key, but that is outside of the scope of this question.

I don't suppose this has to be difficult. You know the sum of elements `0` through `n-1`, so generating `n` is as simple as picking some value larger than that. A cryptographically secure random number generator should work just fine when doing this, making your answer:
``````K[n] = sum(K[0] ... K[n-1]) + random(1, c)
Select some value `c` such that you don't encounter overflow when generating the list, and use that to generate a list as long as you want.
• This is a good answer, and I will probably select it as accepted answer unless someone else places a better answer during the next few days. The most important issue I still have with this approach is what value to select for `c`, because regardless of what (finite) value is selected, you are leaking entropy: the algorithm will then never be able to create a Knapsack having a jump `> c` between consecutive elements. Of course, in practice, the Knapsack cryptography has other problems that make it insecure, but it still is an interesting problem. – Qqwy Sep 24 '16 at 15:54