Superincreasing Sequence

In mathematics, a sequence of positive real numbers $(s_1, s_2, ...)$ is called superincreasing if every element of the sequence is greater than the sum of all previous elements in the sequence.Richard A. Mollin, ''An Introduction to Cryptography (Discrete Mathematical & Applications)'', Chapman & Hall/CRC; 1 edition (August 10, 2000), Bruce Schneier, ''Applied Cryptography: Protocols, Algorithms, and Source Code in C'', pages 463-464, Wiley; 2nd edition (October 18, 1996),

Formally, this condition can be written as
:$s_ > \sum_^n s_j$
for all ''n'' ≥ 1.

Example

For example, (1, 3, 6, 13, 27, 52) is a superincreasing sequence, but (1, 3, 4, 9, 15, 25) is not. The following Python source code tests a sequence of numbers to determine if it is superincreasing:

sequence = , 3, 6, 13, 27, 52total = 0
test = True
for n in sequence:
print("Sum: ", total, "Element: ", n)
if n <= total:
test = False
break
total += n

print("Superincreasing sequence? ", test)

This produces the following output:

Sum: 0 Element: 1
Sum: 1 Element: 3
Sum: 4 Element: 6
Sum: 10 Element: 13
Sum: 23 Element: 27
Sum: 50 Element: 52
Superincreasing sequence? True

See also

* Merkle–Hellman knapsack cryptosystem

References

Cryptography

{{crypto-stub