Числа Веддерберна — Этерингтона и их применение в криптографии и теории деревьев
Wedderburn–Etherington number
Числа Веддерберна-Этерингтона: последовательность целых чисел для подсчета бинарных деревьев. Применение в криптографии и скрытых бэкдорах. SEO-оптимизация.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Числа Уэддерберна — Этерингтона — это целочисленная последовательность, названная в честь Айвора Малкольма Хэддона Этерингтона и Джозефа Уэддерберна, которая может использоваться для подсчёта определённых видов двоичных деревьев. Первые несколько чисел в последовательности: 0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011.
The Wedderburn–Etherington numbers are an integer sequence named for Ivor Malcolm Haddon Etherington and Joseph Wedderburn that can be used to count certain kinds of binary trees. The first few numbers in the sequence are
0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011,
Приложения
использовать числа Уэддерберна — Этерингтона в качестве части конструкции системы шифрования, содержащей скрытую лазейку. Если входные данные, предназначенные для шифрования их системой, могут быть достаточно сжаты кодированием Хаффмана, они заменяются сжатой формой вместе с дополнительной информацией, раскрывающей ключевые данные злоумышленнику. В этой системе структура дерева кодирования Хаффмана описывается как дерево Оттера и кодируется двоичным числом в интервале от 0 до числа Уэддерберна — Этерингтона, соответствующего количеству символов в коде. Таким образом, кодирование использует очень небольшое количество бит – логарифм по основанию 2 от числа Уэддерберна — Этерингтона. Описывается аналогичный метод кодирования для корневых неупорядоченных двоичных деревьев, основанный на разбиении деревьев на небольшие поддеревья и кодировании каждого поддерева числом, ограниченным числом Уэддерберна — Этерингтона для его размера. Их схема позволяет кодировать эти деревья, используя количество бит, близкое к теоретическому нижнему пределу информации (логарифму по основанию 2 от числа Уэддерберна — Этерингтона), при этом обеспечивая операции навигации по дереву за постоянное время. Используются неупорядоченные двоичные деревья, а также тот факт, что числа Уэддерберна — Этерингтона значительно меньше чисел, подсчитывающих упорядоченные двоичные деревья, для существенного сокращения количества членов в ряде, представляющем решение определенных дифференциальных уравнений.
use the Wedderburn–Etherington numbers as part of a design for an encryption system containing a hidden backdoor. When an input to be encrypted by their system can be sufficiently compressed by Huffman coding, it is replaced by the compressed form together with additional information that leaks key data to the attacker. In this system, the shape of the Huffman coding tree is described as an Otter tree and encoded as a binary number in the interval from 0 to the Wedderburn–Etherington number for the number of symbols in the code. In this way, the encoding uses a very small number of bits, the base 2 logarithm of the Wedderburn–Etherington number. describe a similar encoding technique for rooted unordered binary trees, based on partitioning the trees into small subtrees and encoding each subtree as a number bounded by the Wedderburn–Etherington number for its size. Their scheme allows these trees to be encoded in a number of bits that is close to the information theoretic lower bound (the base 2 logarithm of the Wedderburn–Etherington number) while still allowing constant time navigation operations within the tree. use unordered binary trees, and the fact that the Wedderburn–Etherington numbers are significantly smaller than the numbers that count ordered binary trees, to significantly reduce the number of terms in a series representation of the solution to certain differential equations.