Properties of bent functions with minimal distance.pdf Здесь и далее пусть n - четное натуральное число. Обозначим:- Еп - множество двоичных векторов длинны n;- F n - множество всех булевых функций от n переменных;- нелинейность - расстояние Хэмминга до класса аффинных функций;- бент-функции - булевы функции от четного числа переменных, обладающие максимальнойнелинейностью;- Bn - множество всех бент-функций от n переменных;- D ( f , g) = {x . Еп 1 / (x) = g ( x ) } где f , g . F n;- / аффинна на D , если для некоторых w0 . Еn, c . Е и для любого x . D выполняется/ (x) = w0 ■ x ф c, где f . F n, D С En;- d(A) - минимальное расстояние между двумя функциями в классе A С F n;- U - многообразие в Еn, т. е. U = х0 ф L, где L - подпространство в Еn, x0 . Еn.Имеет место нижняя оценка на расстояние между бент-функциями.Теорем а 1. Справедливо d (B n) ^ 2n/2.Следующая теорема дает критерий расположения функций на расстоянии 2n/2.Теорем а 2. Пусть / , g . F n, / - бент-функция, |D ( /, g)| = 2n/2. Тогда g - бент-функция тогда и только тогда, когда множество D ( /, g) - линейное многообразиеразмерности n/2 и / на нем аффинна.С л ед стви е 1. Минимальное расстояние в классе бент-функций равно 2n/2.Определим следующие множества.- Laii ( f ) - множество всевозможных подпространств в En размерности n/2, на которыхf аффинна;- Uaii( f ) - множество всевозможных многообразий в En размерности n/2, на которыхf аффинна.По предыдущей теореме все бент-функции на минимальном расстоянии от заданнойбент-функции описываются следующим образом.С л ед стви е 2. Пусть f Е B n. Тогда функция g Е B n находится на минимальномрасстоянии от f тогда и только тогда, когда g представляется в следующем виде:g (x) = f (x) ® Iu (x), для некоторого U Е Uall( f ),где Iu (x) - индикатор множества U.В связи с предложенным описанием бент-функций на минимальном расстоянии отзаданной бент-функции рассмотрим индикаторы линейных многообразий:Лемма 1. Пусть U - многообразие в En размерности n/2. Тогда индикатор Uможно представить в следующем виде:Iu(x) = (a! ■ x 0 c1 ) ■ . .. ■ (an/2 ■ x 0 cn/2)для некоторых a* Е En и c Е {0 ,1 }.У тв ерж д ен и е 1. Любая функция из B 6 имеет непустое Lall.У тв ерж д ен и е 2. Любая функция из B g степени не больше 3 имеет непустое Lall.Для доказательства этих утверждений использовались аффинно неэквивалентныебент-функции, приведенные в [2].У тв ерж д ен и е 3. Любая функция из B n, аффинно эквивалентная функции в виделинейного разветвления с индексом линейности n/2, имеет непустое Lall. В частности,любая функция из класса Мэйорана - Мак-Фарланда имеет непустое Lall.Описание класса B n в виде линейного разветвления можно найти в [1], класс Мэйорана- Мак-Фарланда в [3].У тв ерж д ен и е 4. Существуют бент-функции от 8 переменных, имеющие непустоеLall, которые не являются аффинно эквивалентными функциям в виде линейногоразветвления с индексом линейности 4.

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