Сверхвозрастающая последовательность

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Сверхвозрастающей называется последовательность, каждый член которой больше суммы всех предыдущих членов. Более формально, последовательность положительных целых чисел s_1, s_2, \dots - сверхвозрастающая, если выполнено условие[1][2], :

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

Данный класс последовательностей широко используется в ранцевой криптосистеме Меркля-Хеллмана.

Например, (1,3,6,13,27,52) является сверхвозрастающей, а (1,3,4,9,15,25) — нет.

Примечания[править | править вики-текст]

  1. Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematical & Applications), Chapman & Hall/CRC; 1 edition (August 10, 2000), ISBN 1-58488-127-5
  2. Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 463-464, Wiley; 2nd edition (October 18, 1996), ISBN 0-471-11709-9

Ссылки[править | править вики-текст]