An upper bound for the number of bent functions at the distance 2 from an arbitrary bent function in.pdf Функция f : Zn ^ Z2 называется булевой функцией от n переменных. Булева функция называется аффинной, если степень её алгебраической нормальной формы не превосходит 1, и квадратичной, если степень равна 2. Заметим, что любая аффинная функция от n переменных представима в виде f (x) = (a, x) ф c, где a Е Zn; c Е Z2; (a, x) = aixi ф... фanxn. Расстояние между двумя булевыми функциями от n переменных- расстояние Хэмминга между векторами их значений. Бент-функция - булева функция от чётного числа переменных, находящаяся на максимально возможном расстоянии от множества всех аффинных функций. Подробнее о бент-функциях можно узнать в работах [1, 2]. Множество s ф D = {s ф x : x Е D} называется сдвигом множества D С Zn, s Е Zn. Аффинное подпространство Zn - сдвиг некоторого линейного подпространства Zn. Размерностью аффинного подпространства называется размерность соответствующего линейного подпространства. Для краткости будем называть аффинное подпространство просто подпространством. Булева функция f от n переменных аффинна на подпространстве L С Zn, если для некоторых a E Zn и c E Z2 верно, что f (x) = (а, я) ©c для всех x E L. Булева функция f называется аффинно расщепляемой по подпространству L, если она аффинна на всех сдвигах L. Аффинность булевых функций на подпространствах рассматривали М. Л. Буряков, О. А. Логачев, А. А. Сальников, С. В. Смышляев, В. В. Ященко [1, 3, 4], а также применительно к бент-функциям Х. Доббертин, К. Карле и П. Шарпин [5-7]. Введём следующее понятие. Определение 1. Булева функция f от n переменных называется полностью аффинно расщепляемой порядка k, 2 ^ k ^ n, если она аффинна хотя бы на одном подпространстве Zn размерности k и аффинно расщепляема по всем подпространствам размерности k, на которых она аффинна. Приведём примеры полностью аффинно расщепляемых функций. Утверждение 1. Справедливы следующие утверждения: (i) Любая квадратичная функция от n переменных является полностью аффинно расщепляемой порядка k при 2 ^ k ^ |~n/2]. (ii) Функция g(x1,... ,Xn) = Х1Х2 © Х3Х4 © ... © X2n-2k-1X2n-2k, где |~n/2] ^ k < n, является полностью аффинно расщепляемой порядка k. (iii) Булева функция является полностью аффинно расщепляемой любого возможного порядка тогда и только тогда, когда она аффинная. В работе [8] установлено, что все полностью аффинно расщепляемые функции порядка |~n/2] являются аффинными или квадратичными (n - число переменных). В данной работе мы обобщаем этот результат. Теорема 1. Пусть f - булева функция от n переменных и f полностью аффинно расщепляемая порядка k, 2 ^ k < n. Тогда (i) f либо аффинная, либо квадратичная; (ii) если k ^ |~n/2] и f не является полностью аффинно расщепляемой порядка k+1, то f аффинно эквивалентна функции g(x1,... , xn) = x1x2 © x3x4 © ... © x2n-2k-1x2n-2k. Напомним, что две булевы функции f и g от n переменных называются аффинно эквивалентными, если существует невырожденная двоичная матрица A размера n х n, вектор b E Zn и аффинная функция £ от n переменных, такие, что f (x) = g(Ax © b) © © £(x) для всех x E Zn. Известно [5], что если f - бент-функция от 2k переменных, L - подпространство Z2k размерности k и f аффинна на L, то f © IndL также является бент-функцией, где Indi - характеристическая функция множества L. В работе [9] доказано, что все бент-функции на расстоянии 2k от бент-функции f можно построить таким способом. Заметим также, что 2k является минимальным возможным расстоянием между двумя бент-функциями от 2k переменных. Таким образом, подпространства размерности k, на которых бент-функция аффинна, представляют особый интерес. В данной работе получена верхняя оценка числа бент-функций на расстоянии 2k от произвольной бент-функции. Теорема 2. Пусть f - произвольная бент-функция от 2k переменных. Тогда существует не более чем 2k(21 + 1) • ... • (2k + 1) бент-функций на расстоянии 2k от f. При этом оценка достигается, если и только если f - квадратичная бент-функция. Достижимость оценки только на квадратичных бент-функциях следует из теоремы 1.

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