DOI: 10.17587/prin.8.76-87

УДК: 519.722

Об эффективном алгоритме решения уравнения действия элемента группы Джевонса над булевыми функциями

А. М. Кукарцев, ст. преподаватель, e-mail: amkukarcev@yandex.ru, А. А. Кузнецов, д-р физ.-мат. наук, проф., e-mail: kuznetsov@sibsau.ru, Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, г. Красноярск

Действие группы Джевонса над булевыми функциями интранзитивно и разбивает все множество на орбиты мощности равной, в подавляющем большинстве случаев, порядку группы 2ⁿn!, где n — число аргументов функции. Вычисление действующего элемента группы, связывающего две функции в одной орбите, является сложнорешаемой математической задачей. Поэтому действие группы Джевонса над булевыми функциями используется как криптографический примитив в алгоритмах шифрования, основывающихся на управляемых операциях, где ключом является действующий элемент группы. В настоящей работе предложен эффективный алгоритм вычисления действующего элемента группы, связывающего две функции за время меньшее, чем тривиальный алгоритм (т. е. полный перебор). Алгоритм использует частотные свойства действия группы Джевонса над булевыми функциями. Приведена эмпирическая оценка сложности предлагаемого алгоритма, основывающаяся на специально разработанном спектральном анализе булевых функций.

Ключевые слова: действие группы на множестве, частотный анализ, группа Джевонса, булевы функции, уравнения действия группы на множестве

Стр. 76–87

Работа выполнена при поддержке гранта Президента РФ (проект МД-3952.2015.9).

Ссылка для цитирования:
Kukartsev A. M., Kuznetsov A. A. On the Fast Solution of the Jevons Group Action equation on Boolean functions, Programmnaya Ingeneria, 2017, vol. 8, no. 2, pp. 76—87.