?.pdf Бент-функции - это булевы функции, максимально удаленные от класса аффин-ных функций. Впервые бент-функции были рассмотрены О. Ротхаусом [1]. Бент-функ-ции имеют огромное число приложений: в криптографии, теории кодирования, теорииинформации. Тем не менее для них до сих пор существует много нерешенных про-блем. Одна из наиболее важных проблем - описание всех бент-функций, в частностинахождение конструкций для бент-функций.В работе рассматривается получение бент-функций на минимальном расстоянии отквадратичной бент-функции. В [2] показано, что две бент-функции от 2k переменныхнаходятся на минимальном расстоянии тогда и только тогда, когда они отличаются нааффинном подпространстве размерности k и обе функции на нем аффинны. В даннойработе описываются все бент-функции на минимальном расстоянии от квадратичнойбент-функции (x1xk+1 ф x2xk+2 ф ... ф xkx2k), а также подсчитывается число бент-функций на минимальном расстоянии от произвольной квадратичной бент-функции.Пусть A - произвольная матрица; через a^) будем обозначать её i-й столбец. Бу-дем описывать линейные подпространства с помощью базисов Гаусса - Жордана. От-метим, что в наших обозначениях базисные векторы являются столбцами базиснойматрицы.Определение 1. Пусть G - матрица с k столбцами, образованная векторамиU(1),... ,U(k) длины n. Через /(u(j)) обозначим min{j : = 0}. Матрица G являетсябазисом Гаусса - Жордана подпространства размерности k в пространстве размерно-сти n, если выполняются следующие условия:1) если i1 < i2, то /(u(j1)) < l(u(i2));2) если i1 = i2, то U(ii)Z( ) = 0.В этом случае через /(G) обозначим множество [/(u(1)),..., /(u(k))}. Все строкиматрицы G с номерами из множества /(G) будем называть ведущими строками. Всеостальные строки будем называть неведущими. Через LG обозначим подпространствос базисом u(1),..., u(k). Заметим, что столбцы матрицы G действительно являются ба-зисными векторами пространства Lg, а матрицу GT называют также редуцированнойступенчатой матрицей.Известно, что любое линейное подпространство имеет ровно один базис Гаусса -Жордана.Введем определение допустимого базиса Гаусса - Жордана. Пусть базис Гаусса -Жордана G для подпространства размерности k в пространстве размерности 2k имеетследующий вид:где матрица A размера k х t не содержит нулевых столбцов, а матрица Y имеет размерk х (k - t). Заметим, что матрицы A и Y являются базисами Гаусса - Жордана. ПустьLy = L^. Удалим из матрицы A все строки с номерами из /(Y). Пусть все оставши-еся строки образуют матрицу A'. Аналогичные действия проделаем и с матрицей Z:удалим все строки с номерами из /(Y) и образуем из оставшихся строк матрицу Z'.Заметим, что все удаленные из матрицы Z строки являются нулевыми, так как Gявляется базисом Гаусса - Жордана. Таким образом, получили матрицы A' и Z' раз-мера t х t. Базис Гаусса - Жордана G назовем допустимым, если t ^ 1 или элементыматрицы Z' при t ^ 2 являются решениями следующей системы уравнений с матрицейразмера (t(t - 1)/2) х t2:Следующая теорема описывает все бент-функции на минимальном расстоянии отквадратичной бент-функции.Теорема 1. Для бент-функции f (x) = x1xk+1 ф x2xk+2 ф ... ф xkx2k функцияf (x) ф Indi (x) является бент-функцией на минимальном расстоянии от f (x) тогда итолько тогда, когда множество L является линейным подпространством с допустимымбазисом Гаусса - Жордана или сдвигом такого подпространства.( а'(2)Т а'(1)Т 0 0 ... 0 \ ( \Z (2)а'(4)Т 0 0 ... 0 а'(1)Т0 а'(э)Т а'(2)Т 0 ... 00 а'(4)Т 0 ... 0 а'(2)Т0.V 0 0 0 ... а'(*)Т а' ( * - 1 ) / V z'(t) )Теорема 2. Любая квадратичная бент-функция от 2k переменных имеет ровно2k (21 + 1) ... (2k + 1) бент-функций на минимальном расстоянии 2k.Заметим, что число бент-функций от 2k переменных на минимальном расстоянииот заданной бент-функции можно оценить сверху числом 2k +2k (это оценка свер-ху числа всевозможных аффинных подпространств размерности k), а число бент-функций на минимальном расстоянии от квадратичной бент-функции асимптотическиравно C 2k(k+3)/2. Таким образом, число бент-функций на минимальном расстоянии отквадратичной бент-функции больше, чем корень из этой тривиальной верхней оценки.

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