Properties of subfunctions of self-dual bent functions.pdf Через F2n обозначим линейное пространство всех двоичных векторов длины n над полем F2. Булевой функцией от n переменных называется отображение вида Fn F2. Множество всех булевых функций от n переменных обозначается через Fn. Характеристическим вектором (характеристической последовательностью) булевой функции f Е Fn называется вектор F (-1)f = ((-1)f(0), (-1)f(1),..., (-1)f(2n-1)) G {±1}2n , где (f (0), f (1),..., f (2n - 1)) G Л - вектор значений функции f. Для каждой пары n x,y G Fn через (x,y) обозначим значение ф xiyi. Преобразованием Уолша - Адамара i=1 булевой функции f от n переменных называется целочисленная функция Wf : Fn Z, заданная равенством Wf (y) = £ (-1)f(x)®n Булева функция g от нечётного числа переменных m называется почти бент-функ-цией, если Wf (y) G {0, ±2(m+1)/2} для каждого y G Fn. Булева функция f от чётного числа переменных n называется почти бент-функцией, если Wf(y) G 0, ±2(n+2)/2 для каждого y G F2n. Булева функция f от чётного числа переменных n называется бент-функци-ей, если |Wf(y)| = 2n/2 для каждого y G F2n [1]. Для множества бент-функций от n переменных используется обозначение Bn. Для каждой f G Bn из соотношения Wf(y) = (-1)f(y)2n/2 однозначным образом определяется дуальная к ней бент-функция f G Bn, значения которой находятся из соответствия для каждого y G Fn. Бент-функция f называется самодуальной (антисамодуальной), если f = f (соответственно f = f ф 1). Множество самодуальных бент-функций от n переменных обозначаются через SBn+. Открытой проблемой является полная характеризация и описание класса самоду-альных бент-функций. Данные вопросы исследовались в ряде работ. В частности, в [2] приведена аффинная классификация самодуальных бент-функций от 2, 4, 6 переменных и всех квадратичных самодуальных бент-функций от 8 переменных относительно преобразования, сохраняющего самодуальность. В работе [3] приведена классификация всех квадратичных самодуальных бент-функций. Аффинную классификацию квадратичных и кубических самодуальных бент-функций от 8 переменных относительно преобразования, сохраняющего самодуальность, можно найти в [4]. В работах [5, 6] представлены конструкции самодуальных бент-функций. В настоящей работе исследованы подфункции самодуальных бент-функций, полученные фиксацией первой переменной, а также первых двух переменных. Другими словами, если f - вектор значений булевой функции f, то упомянутые подфункции есть в точности булевы функции с векторами значений fi в представлении f = (f0, f1 , . . . , f2k-1 ) для k = 1, 2 соответственно. Предложены новые конструкции, а также новая итеративная нижняя оценка числа самодуальных бент-функций. 1. Подфункции от n - 1 переменной Известно, что подфункции от n - 1 переменной каждой бент-функции являются почти бент-функциями, при этом носители их спектров Уолша - Адамара не пересекаются [7]. Отношением Рэлея булевой функции f от n переменных называется число Sf У (-i)f(x)®f(y)® V (-i)f(y)wf(y). x,y&2 y&?2 Применительно к бент-функциям данная характеристика изучалась в работе [8]. Она представляет интерес в силу того, что число Sf полностью характеризует расстояние Хэмминга между бент-функцией и дуальной к ней. Заметим, что задача поиска максимального (минимального) значения отношения Рэлея решена лишь для случая чётного числа переменных. Для нечётного случая она является открытой проблемой. Известно [2], что для каждой булевой функции f от чётного числа n переменных справедливо |Sf | 23n/2, при этом равенство достигается в том и только в том случае, когда f - самодуальная ( |23"/2j или антисамодуальная (-23n/2^ бент-функ-ция. Нетрудно видеть, что в случае чётного чения отношения Рэлея достигаются лишь рых (-1)f(y)Wf(y) = 2n/2 или (-1)f(y)Wf(y) = -2n/2 при каждом y G F числа переменных экстремальные зна-на тех булевых функциях, для котоn. Введём следующее понятие самодуальности почти бент-функции от нечётного числа переменных. Пусть m - нечётное положительное число. Почти бент-функцию g от m переменных будем называть самодуальной, если ' W(y) » 0 для любого y G F2m. В свою очередь, функция g называется антисамодуальной почти бент-функцией, если ' W(y) « 0 для любого y G F2m. Содержательно оба определения описывают ситуации, когда знаки коэффициентов Уолша - Адамара и значения характеристического вектора почти бент-функции согласованы. Можно показать, что Утверждение 1. Пусть g - почти бент-функция от m переменных, тогда |Sg | < 2(3m-1)/2, при этом равенство достигается, если и только если g - самодуальная (+2(3m-1)/2) или антисамодуальная -2(3m-1)/2 почти бент-функция. То есть (анти-)самодуальные почти бент-функции от нечётного числа переменных на множестве почти бент-функций, так же как и самодуальные бент-функции на множестве булевых функций от чётного числа переменных, являются экстремальными объектами в спектральном смысле. Понятия самодуальности для чётного и нечётного числа переменных тесно связаны, что показывает следущая Теорема 1. Между множествами самодуальных бент-функций от n 4 переменных и множеством (анти-)самодуальных почти бент-функций от n - 1 переменных существует взаимно однозначное соответствие. Упомянутая связь устанавливается на основе отображения, которое каждой само-дуальной бент-функции ставит в соответствие её подфункцию, получаемую фиксацией первой координаты. Таким образом, подфункциями от n - 1 переменной, получаемыми фиксацией первой координаты, являются самодуальные почти бент-функции, и только они. 2. Свойства подфункций от n - 2 переменных Известно [9], что для каждой бент-функции от n переменных все её подфункции от n - 2 переменных имеют одинаковые спектры Уолша - Адамара. Более того, все подфункции являются бент-функциями, либо все являются почти бент-функциями, либо их спектры Уолша - Адамара состоят из чисел 0, ±2(n-2)/2, ±2n/2. Случай, когда все подфункции являются бент-функциями, ведёт к итеративной конструкции бент функции от n + 2 переменных на основе четырёх бент-функций от n переменных. В работе [10] найдены необходимые и достаточные условия того, что конкатенация векторов значений четырёх бент-функций от n переменных даёт вектор значений бент-функции от n + 2 переменных. Известны две итеративные конструкции самодуальных бент-функций от n + 2 переменных, в основе которых лежит конкатенация четырёх векторов значений бент-функций от n переменных. Они представлены ниже: - конструкция C1: (h, h,h,h ф 1), где h - бент-функция от n переменных [2]; - конструкция C2: (f,g ф 1,g,f), где f - самодуальная, а g - антисамодуальная бент-функции от n переменных [11]. Сумма мощностей данных непересекающихся конструкций C1 и C2 даёт нижнюю оценку |Bn-2| + |SB+-2| числа самодуальных бент-функций. Прямые вычисления показывают, что данная оценка превосходит другие известные оценки. Очевидно, что для обоих конструкций характеристические векторы подфункций образуют линейно зависимые множества. В настоящей работе доказано утверждение, обобщающее данный факт: Теорема 2. Если характеристические векторы подфункций f0, f1, f2, f3 самоду-альной бент-функции f линейно зависимы, то данные подфункции являются бент-функциями. Теорема 2 даёт достаточное условие того, что все подфункции, полученные фиксацией первых двух переменных, являются бент-функциями. Отметим, что для случая n = 4 данное условие также является достаточным. 3. Новые конструкции и оценка числа самодуальных бент-функций В настоящей работе мы предлагаем три новых конструкции C3 , C4 и C5 самоду-альных бент-функций. В данных конструкциях используются бент-функции от n - 4 переменных. Пусть h - бент-функция от n - 4 переменных, f - самодуальная и g - антисамодуальная бент-функции от n - 4 переменных. Опишем конструкции: - C3: вектор значений функции имеет вид (h^g ф 1,h h,f,f ф 1, h, h,f ф l,f, h,h ф 1,g,g ф l,h ф 1); все подфункции от n - 2 переменных являются бент-функциями; - C4: вектор значений функции имеет вид (М, h,f,g ф 1,h,f ф 1 h, h,f ф 1,h ф 1,g,f, h,g ф l,h ф 1); подфункции от n - 2 переменных являются бент-функциями тогда и только тогда, когда h ф h ф f ф g = 0. Таким образом, данная конструкция даёт класс самоду-альных бент-функций, которые нельзя представить в виде конкатенации четырёх бент-функций; - C5: вектор значений функции имеет вид (h, h ф 1, h, h, h, h, h ф 1, h, h, h, h ф 1, h, h ф 1, h, h ф 1, h ф 1); все подфункции от n - 2 переменных являются бент-функциями. На основе анализа данных конструкций получена Теорема 3. Число самодуальных бент-функций от n 6 переменных не меньше чем |Bn_2| + |SB+-212 + |Bn-4| (2 ISB+-412 + 1) - 2 |SB+_41. Таким образом, известная итеративная нижняя оценка увеличивается на слагаемое, соответствующее самодуальным бент-функциям от n - 4 переменных. 4. Линейная независимость характеристических векторов подфункций Конструкции, предложенные в работе, позволяют однозначно ответить на вопрос о возможности обращения теоремы 2 для случая n 6. Теорема 4. Для каждого чётного n 6 существуют самодуальные бент-функции от n переменных, подфункции которых образуют линейно независимые множества векторов. Таким образом, обращение теоремы 2 не имеет места при n 6, то есть линейная зависимость характеристических векторов не является необходимым условием, а обеспечивает лишь достаточное условие того, что подфункции от n - 2 переменных являются бент-функциями.

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