In
mathematics, a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of positive
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s
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
:
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
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
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 The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems. It was published by Ralph Merkle and Martin Hellman in 1978. A polynomial time attack was published by Adi Shamir in 1984. As a result, the cryptosyste ...
References
Cryptography
{{crypto-stub