The degree of proximity of the boolean function reduced representation to the class of monomial functions according to b.pdf Пусть F2 - поле из двух элементов с единицей e, F2n - его расширение степениn-in . N, trn (a) = a 2 - функция след из F2n в F2. Для целых ti , t2 через (ti , t2) будемk= 0обозначать их неотрицательный наибольший общий делитель.Основные результаты работы получены с использованием представления булевыхфункций от n переменных в виде многочленов над полем F2n, принимающих значенияв поле F2 (так называемого «приведенного представления»). Описание механизмаполучения подобного представления можно найти в [1].Пусть ^ (xo,Xi, ...,xn-1) - булева функция от n переменных, (ео,е1, ...,еп-1) - базисвекторного пространства (F2n )^2. Как следует из результатов работы [1], существуетмногочлен Ф(х) над полем F2n такой, что для каждого x Е F2n выполненоп- 1trn (Ф(х)) = ^ (x0,x 1, ...,xn-1), где x = Xj ■ e j . Для каждой линейной булевой функ-j=oции ее приведенное представление имеет вид trn (ax) для некоторого а Е F2n.Нас будет интересовать удаленность (в смысле расстояния Хемминга между векторамизначений) булевой функции от некоторого множества функций - класса приближений.В качестве показателя близости приближающей функции G (x) : F2n ^ F2к исходной функции F (x) будем использовать величину A (F, G) = ^2 (-1)F(x)+G(x).Если функция G (x) линейная, то A (F, G) есть соответствующий коэффициентУолша - Адамара функции F (x) (см., например, [2]). Для коэффициентов Уолша -Адамара произвольной функции справедлива оценкаmax {|A (F, trn (ax))| : a Е F2n} ^ 2n. (1)Функции, для которых неравенство (1) обращается в равенство, существуют толькодля четных значений n и носят название бент-функций.Функция принадлежит классу мономиальных функций, если ее приведенное представлениеимеет вид L ^ (x) = trn (a ■ x5) для некоторых а Е F2n, 8 Е N ([1, 3]). Изоценки (1) следует справедливость неравенстваmax { | A (F, L ^ ) \ : 8 Е N, (8, 2n - 1) = 1, а Е F2n } ^ 2n. (2)Функции, для которых достигается оценка (2), называют гипербент-функци-ями [1, 3]. Класс бент-функций инвариантен относительно невырожденной линейнойзамены переменных (см., например, [2]). В этом смысле основной результат даннойработы демонстрирует отличие свойств бент- и гипербент-функций.Рассмотрим вопрос о том, как влияет выбор базиса, в котором строится приведенноепредставление булевой функции, на его (представления) свойство «быть гипер-бент-функцией». Для d Е 1, 2n - 2 через обозначим отображение на F2n такое, чтодля любого x Е F2n выполнено (x) = x d. Для различных d1 ,d" Е 1, 2n - 2, каждое изкоторых взаимно просто с 2n - 1, отображения п#' и п#'' задают различные подстановкина F2n. Кроме того, для любых d', d" Е 1, 2n - 2 выполнено п#'п#" = п#'#" mod (2п-1).Положим D = {п# | (d, 2n - 1) = 1 } и заметим, что это множество с операцией умноженияявляется абелевой группой. Зафиксируем базис (F2n )^ . Пусть отображение Tставит в соответствие каждому элементу F2n строку координат его разложения по данномубазису, задавая биективное соответствие между F2n и (F2)n. Через х обозначиминдуцируемый отображением T изоморфизм групп S (F2n \ {0 }) и S ^(F2)n \ | 0 |^.Лемма 1. Пусть n > 4, т - нечетная подстановка на множестве F2n\ {0 }, такая,что т2 не принадлежит х -1 (GL (n, 2)). Тогда т в объединении с х -1 (GL (n, 2)) в ихдействии на F2n \ {0 } порождает группу S (F2n \ {0 }).У тв ерж д ен и е 1. Для n > 4 существует d Е 1, 2n - 2, такое, что п# в объединениис X-1 (GL (n, 2)) в их действии на F2n\ {0 } порождает группу S (F2n\ {0 }).С л ед стви е 1. Для n > 4 группа D в объединении с х -1 (GL (n, 2)) в их действиина F2n \ {0 } порождает группу S (F2n \ {0 }).Теорем а 1.1) Для любой бент-функции от 4 переменных существуют базисы ^0^, ^i^, е2^, ^3^)/ (2) (2) (2) (2)\ ш и ( ^0 , е1 , .2 ,.з ) векторного пространства (F 24ч)F , такие, что приведенное представлениеданной функции в первом базисе является, а во втором не является гипербент-функцией.2) Для любого четного n > 4 существуют функции от n переменных, для каждойиз которых можно найти два базиса векторного пространства (F2n )^ , таких, что приведенноепредставление функции в первом базисе является, а во втором не являетсягипербент-функцией.

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