On the minimal distance graph connectivity for bent functions.pdf Отображение / : Fn ^ F2 называется булевой функцией от n переменных. Аффинной булевой функцией называется функция вида (a, x) ф с, где а е Fn, с е F2 и (а, x) = aixi ф a2x2 ф ... ф anxn. Расстоянием Хэмминга dist(/, g) между двумя булевыми функциями / и g от n переменных называется количество x е Fn, таких, что /(x) = g(x). Бент-функцией называется булева функция от чётного числа переменных, находящаяся на максимально возможном расстоянии от множества всех аффинных функций. Обозначим через множество всех бент-функций от 2k переменных. Бент-функции предложены О. Ротхаусом [1]. Они имеют большое число приложений в алгебре, комбинаторике, теории кодирования, криптографии [2]. Граф GB2k = (V, E) называется графом минимальных расстояний множества бент-функций, если V = B2k и (/, g) е E тогда и только тогда, когда dist(/, g) = 2k. Заметим, что 2k является минимально возможным расстоянием между двумя бент-функциями от 2k переменных. Напомним, что функции следующего вида являются бент-функциями и образуют класс Мэйорана - МакФарланда M2k [3]: /(x,y) = (x,n(y)) ф ^(y), где x,y е F^; п - подстановка на множестве F^; ^ - произвольная булева функция от k переменных. Пусть множество М2& содержит все функции вида /(Ax ф b), где / е М2&; A - обратимая двоичная матрица размера 2k х 2k и b е F^. Другими словами, любая функция из M2k является бент-функцией, аффинно эквивалентной некоторой бент-функции из класса Мэйорана - МакФарланда. Заметим, что / ф £ лежит в М2& для любой / е M2k и любой аффинной функции £ от 2k переменных. Обозначим через GM2k подграф графа GB2k, порождённый множеством вершин M2fc. Известно [4], что максимальная степень вершины в графах GB2k и GM2k равна 2k(2l + 1)(22 + 1)... (2k + 1), причём любая вершина максимальной степени является квадратичной бент-функцией. В данной работе рассматривается связность графов GB2k и GM2k. Утверждение 1. Степень любой вершины графа GM2k не меньше, чем 22fc+i - 2k. Теорема 1. Граф GM2k является связным для любого k ^ 1. Следствие 1. Граф GM2k является рёберно 3-связным. Следствие 2. Графы GB2, GB4 и GB являются связными. Отметим, что в общем случае граф GB2k не является связным, поскольку он может содержать изолированные вершины. В частности, это справедливо при 2k ^ 14.

Скачать электронную версию публикации