Том 14, серия 1, номер 4, 2007 г., Стр. 76-102

УДК 519.7+519.1
Н. Н. Токарева
Бент-функции с более сильными свойствами нелинейности: $k$-бент-функции

Аннотация:
Вводится понятие $k$-бент-функции – булевой функции от чётного числа переменных $m$, одинаково плохо аппроксимируемой всеми функциями вида $\langle\mathbf u,\mathbf v\rangle_j\oplus a$, где $\mathbf u,\mathbf v\in\mathbb Z_2^m$, $a\in\mathbb Z_2$, при всех целых $j$, $1\leqslant j\leqslant k$, где $\langle\cdot,\,\cdot\rangle_j$ является аналогом скалярного произведения векторов и $k$ меняется от 1 до $m/2$. Произведения $\langle\cdot,\,\cdot\rangle_k$, $1\leqslant k\leqslant m/2$, определяются с помощью специальной серии двоичных кодов типа Адамара $A_m^k$ длины $2^m$, а именно векторы значений функций $\langle\mathbf u,\mathbf v\rangle_k\oplus a$, где $a\in\mathbb Z_2$, являются кодовыми словами кода $A_m^k$. Коды $A_m^k$ строятся с помощью подкодов $\mathbb Z_4$-линейных кодов типа Адамара длины $2^{m+1}$, классификация которых была дана Д. С. Кротовым (2001). При этом код $A_m^1$ линеен и коды $A_m^1,\dots, A_m^{m/2}$ попарно неэквивалентны. На каждом коде $A_m^k$ определяется своя групповая операция $\bullet$. Поэтому можно считать, что $k$-бент-функции – это функции максимально нелинейные при $k$ различных смыслах линейности одновременно. Обычные бент-функции представляют собой класс 1-бент-функций. Для $1\leqslant\ell<k$ класс $k$-бент-функций является собственным подклассом класса $\ell$-бент-функций. В статье приводятся способы построения $k$-бент-функций и рассматриваются их свойства. Показано, что существуют $k$-бент-функции с любой степенью нелинейности $d$, где $2\leqslant d \leqslant\max\{2,\frac m2-k+1\}$. Для каждого $k$ определено подмножество $\mathfrak F_m^k$ множества булевых функций $\mathfrak F_m$, на котором понятия $k$-бент-функции и 1-бент-функции совпадают.
Библ. 39.

Токарева Н. Н. ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: tokareva@math.nsc.ru

Статья поступила 11 мая 2007 г.