Properties of p-ary bent functions that are at minimal distance from each other.pdf Введение Рассмотрим конечную абелеву группу G и векторное пространство V(G), состоящее из функций / : G ^ C, со скалярным произведением (/, g) = /(x)g(x). xeG Характерами называются гомоморфизмы группы G в мультипликативную группу поля C, т.е. такие ф е V(G), что 0(x + y) = ф^)ф(у), для любых x,y е G. Характеры абелевой группы G образуют ортогональный базис в V(G). Если G = Z^ то для любого z е Zn характер группы G определяется равенством фг (x) = где £ = e2ni/q и (x,y) = xiyi + ... + xnyn mod q. Характерами прямой суммы двух групп являются всевозможные попарные произведения характеров первой и второй группы. Поскольку любая конечная абелева группа представляется в виде прямой суммы циклических групп, характеры произвольной конечной абелевой группы являются произведениями функций определённого выше вида. Преобразованием Фурье функции из V(G) называется вектор коэффициентов в разложении по базису характеров. Нам будет удобнее определить преобразование Фурье изометричным образом: /(z) = (/, ф)/|G|1/2. Тогда равенство Парсеваля принимает вид ||/1| = II/H и справедлива формула обращения (/(x)) = f (-x). Носителем функции называется множество аргументов, на которых функция принимает ненулевые значения supp(/) = {x Е G : /(x) = 0}. Доказательство следующего утверждения имеется, например, в [1]. Утверждение 1 (принцип неопределённости). Пусть G - конечная абелева группа, тогда |supp(/)||supp(/)| ^ |G|. (1) Причём равенство в формуле (1) достигается только для характеристических функций подгрупп с точностью до естественных преобразований, сохраняющих мощности носителей функции и её фурье-образа. Если p - простое число, то группу Z^ можно рассматривать как n-мерное векторное пространство над полем GF(p). Следствие 1. Пусть G = Z^ и p - простое число. Равенство в формуле (1) достигается, если и только если / = сфхг, где z Е G; c Е C - константа и хГ -характеристическая функция аффинного подпространства Г в G. Известно (см., например, [2, с. 33, лемма 1.1.26]) следующее равенство. Утверждение 2 (тождество Саркара). Пусть p - простое число и Г - линейное подпространство в Z^. Тогда E/(y) = pdimr-n/2 Е /(x). уег жегх Определим свёртку двух функций /, g Е V (G) равенством / *g(z) = Е / (x)g(z-x). xeG Из определения свёртки нетрудно получить известное равенство 7*g = |G|1/2/ ■ ?. (2) 1. Бент-функции Для функций g : Z™ ^ Zq определим преобразование Уолша - Адамара следу- -q ^ ющим образом: (z) = £g (z). Функция / : Z^ ^ Zq называется бент-функцией (q-ичной), если (y)| = 1 для любых y Е Z^, или (что то же самое) £f ■ £f = I, I - функция, всюду равная 1 [3-5]. Из (2) следует, что определение бент-функции эквивалентно равенству £f * £f = |G|x{0}. Отсюда непосредственно вытекает, что матрица A = (az,y), где az,y = £f (z+y), является обобщённой матрицей Адамара, как и матрица H = (hz,y), где = Нетрудно видеть, что невырожденные аффинные преобра зования аргументов бент-функции и прибавление аффинной функции не выводят из класса бент-функций. Бент-функция b называется регулярной, если найдётся функция b' : Z^ ^ Zq, удовлетворяющая равенству £b' = £b. Из формулы обращения следует, что b' также является бент-функцией. Известно следующее Утверждение 3. q-1 1) Е £kj = 0 при k = 0 (mod q); j=0 2) если q - простое, то £ не является корнем многочлена степени меньше q - 1; 3) если q - степень простого числа, то алгебраическая система, полученная присоединением элемента £ к полю рациональных чисел, является полем. Из свойства 3 непосредственно получаем Следствие 2. Если q - степень простого числа и n чётно, то все бент-функции регулярны. Для доказательства следствия нужно использовать то, что число |G|n/2 -целое и линейная комбинация элементов поля содержится в поле. В дальнейшем полагаем p простым, а n чётным. Из свойства 2 утверждения 3 можно получить Следствие 3. Для любых двух p-ичных бент-функций b и b1 справедливо равенство |supp(£b - £ь')| = |supp(£b - £*)|. Для доказательства следствия достаточно проверить, что имеется (p - 1)/2 различных чисел вида |£г - £j |2, i = j, которые независимы над полем рациональных чисел. Отсюда и из утверждения 1, а также следствия 1 имеем Следствие 4. Расстояние Хэмминга между двумя бент-функциями, т. е. число аргументов из Z^", на которых они различаются, не меньше pn/2. Если это расстояние равно pn/2, то разность между ними равна с%г, где c е Zp; Г - аффинное подпространство размерности n/2. Из утверждения 2 можно получить Следствие 5. Если бент-функция b : Z^ ^ Zp аффинна на аффинном подпространстве Г, то dim Г ^ n/2. Следствие 6. Если бент-функция b : Z^ ^ Zp аффинна на аффинном подпространстве размерности n/2, то найдётся ровно p - 1 бент-функций, отличающихся от b только на этом подпространстве. Поскольку аффинные преобразования не выводят из класса бент-функций, при доказательстве следствия 6 достаточно рассматривать содержащие нулевой вектор грани Г размерности n/2 и бент-функции, постоянные на этой грани. Из утверждения 2 видно, что если £ь постоянна на Г, то и £ь постоянна на Г^ и принимает это же значение £k, k е Zp. Нетрудно видеть, что %г± = ХГ. Тогда сумма £ь + (£m - £k)хг, m е Zp, также является бент-функцией. Следствия 4-6 при p =2 доказаны в [6] (следствия 5 и 6 имеются в [7]). В двоичном случае исследованы также возможные (не превышающие двух минимальных) расстояния между двумя бент-функциями [8]. 2. Число бент-функций на минимальном расстоянии от квадратичной Квадратичная форма Q : (GF(q))n ^ GF(q) называется невырожденной, если её ядро {x е (GF(q))n : Vy е (GF(q))n (Q(y + x) = Q(y))} состоит из нуля. Линейное подпространство U в (GF(q))n называется тотально изотропным, если Q(U) = 0. Максимальная размерность тотально изотропного подпространства называется индексом Витта формы Q. При n = 2d максимальный индекс Витта невырожденной квадратичной формы равен d. Все квадратичные формы максимального индекса Витта эквивалентны (переводятся друг в друга невырожденным линейным преобразованием). Одним из представлений такой формы является Q0(vl, ... , vd, ul, ..., ud) = viui + .. .+vdud. Нетрудно показать, что Q0 является бент-функцией (частным примером конструкции Майорана - МакФарланда [5]). Известно (см., например, [9, p. 274, Lemma9.4.1]) следующее Утверждение 4. Число тотально изотропных подпространств максимального d индекса d = n/2 у квадратичной формы Q0 равно П (qd-i + 1). i=i Нетрудно видеть, что если форма Q0 аффинна на некотором аффинном подпространстве, то она аффинна и на любом его смежном классе. При q > 2 если форма Q0 аффинна на некотором линейном подпространстве индекса d, то это подпространство тотально изотропно. Таким образом, форма Q0 аффинна на всех смежных классах тотально изотропных подпространств индекса d и не аффинна на других аффинных подпространствах той же размерности. Из утверждения 4 и следствия 6 имеем Следствие 7. Пусть p - простое, p > 2. Тогда количество p-ичных бент-функций от 2d переменных, находящихся на расстоянии pd от квадратичной формы Q0, равно pd(pd-i + 1) ••• (p + 1)(p - 1). В двоичном случае аналогичное утверждение доказано в [10]. В [11] доказано, что максимальное количество близких соседних бент-функций имеется только у квадратичной бент-функции. Можно предположить, что последнее свойство, характеризующее квадратичные функции, остаётся верным для всех простых p > 2.

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