Superincreasing sequence

Superincreasing sequence

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

Formally, written:

s_{n+1} > sum_{j=1}^n s_j

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 = [1,3,6,13,27,52] sum = 0test = Truefor n in sequence: print "Sum: ", sum, "Element: ", n if n <= sum: test = False break sum = sum + n

print "Superincreasing sequence? ", test

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

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… …   Wikipedia

  • Merkle-Hellman — (MH) was one of the earliest public key cryptosystems and was invented by Ralph Merkle and Martin Hellman in 1978. [Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory , 24(5),… …   Wikipedia

  • сверхвозрастающая последовательность — — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=4638] Тематики защита информации EN superincreasing sequence …   Справочник технического переводчика

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”