Близость к классу мономиальных аппроксимаций приведенного представления булевой функции в зависимости от выбора базиса, в котором оно задано

Как показывает следующий пример, несмотря на то, что операции параллельной композиции регулярных и w-регулярных языков очень похожи, методы решения уравнений для регулярных языков не могут быть напрямую применены при решении уравнений для w-регулярных языков. Рассмотрим w-регулярные языки C = ((¿1 + i2)(ui + W2))*(il«l)! + (*2«2)Ш и S = (¿1 + ¿2)**! (где верхний индекс W означает бесконечную конкатенацию слова) и их множества конечных префиксов Init(C) = ((¿1 + ¿2)(ui + U2))*(*lUl)* + (¿2U2)* и Init(S) = (¿1 + ¿2)*** = (¿1 + ¿2)*. Наибольшим решением уравнения Imt(C) о X = Irnt(S) является регулярный язык Sol = (u1 +u2)*. Как обычно, определим предел регулярного языка L как w-регулярный язык, содержащий каждое бесконечное слово, множество конечных префиксов которого содержится в L. Взяв предел регулярного языка Sol, получим lim(Sol) = (u1 + u2)!. Однако w-язык (u1 + u2)! не является решением уравнения CоX = S, так как (u1 + u2)! содержит слово u!, расширение которого на алфавит I содержит слово (¿2u2)!, а значит, пересечение C П (lim(Sol))^/ будет содержать слово (¿2u2)!, ограничением которого на алфавит I будет слово ¿!, не содержащееся в S. Однако можно показать, что формула наибольшего решения для w-регулярных языков имеет такой же вид, как и при решении уравнения для регулярных языков, т. е. наибольшее решение уравнения C о X = S есть w-язык C о S .В нашем примере наибольшим решением уравнения является w-регулярный язык (u1 + u2)!\u!.

Бушков В. Г. выражает благодарность фонду Бортника за финансовую поддержку по проекту 8858, Евтушенко Н. В. выражает благодарность РФФИ за финансовую поддержку по проекту 06-08-89500.

ЛИТЕРАТУРА

1. Buffalov S., El-Fakih K., Yevtushenko N., et al. Progressive solutions for a parallel automata equation // FORTE’03. Berlin: Springer, 2003. P. 367-382.

2. Yevtushenko N. V., Villa T., Brayton R. K., et al. Sequential synthesis by language equation solving // Intenational Workshop on Logic Synthesis. June, 2000.

3. Глушков В. М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 476 с.

4. Mukund M. Finite-state automata on infinite inputs // The 6th National Seminar on Theorectical Computer Science. Banasthali, Rajasthan, India, 1996. V. 2.

УДК 519.651

БЛИЗОСТЬ К КЛАССУ МОНОМИАЛЬНЫХ АППРОКСИМАЦИЙ ПРИВЕДЕННОГО ПРЕДСТАВЛЕНИЯ БУЛЕВОЙ ФУНКЦИИ В ЗАВИСИМОСТИ ОТ ВЫБОРА БАЗИСА, В КОТОРОМ ОНО ЗАДАНО

А. В. Иванов

Пусть F2 — поле из двух элементов с единицей e, F2n — его расширение степени

n-1

n £ N, tr^ (а) = а2 — функция след из F2n в F2. Для целых t1, t2 через (t1, t2) будем

k=0

обозначать их неотрицательный наибольший общий делитель.

Основные результаты работы получены с использованием представления булевых функций от n переменных в виде многочленов над полем F2n, принимающих значения в поле F2 (так называемого «приведенного представления»). Описание механизма получения подобного представления можно найти в [1].

Пусть ^ (xo,Xi, ...,xn—1) — булева функция от n переменных, (eo,£i, ...,£n—1) — базис векторного пространства (F2n )^2. Как следует из результатов работы [1], существует многочлен Ф(х) над полем F2n такой, что для каждого x G F2n выполнено

П— 1

tr^ (Ф(х)) = (x0,x1, ...,xn—1), где x = Xj • £j. Для каждой линейной булевой функ-

j=o

ции ее приведенное представление имеет вид trn (ax) для некоторого a G F2n.

Нас будет интересовать удаленность (в смысле расстояния Хемминга между векторами значений) булевой функции от некоторого множества функций — класса приближений. В качестве показателя близости приближающей функции G (x) : F2n ^ F2 к исходной функции F (x) будем использовать величину A (F, G) = ^2 (—1)F(x)+G(x).

n

Если функция G (x) линейная, то A (F, G) есть соответствующий коэффициент Уолша — Адамара функции F (x) (см., например, [2]). Для коэффициентов Уолша — Адамара произвольной функции справедлива оценка

Функции, для которых неравенство (1) обращается в равенство, существуют только для четных значений n и носят название бент-функций.

Функция принадлежит классу мономиальных функций, если ее приведенное представление имеет вид L0^ (x) = trn (a • x5) для некоторых a G F2n, 8 G N ([1, 3]). Из оценки (1) следует справедливость неравенства

Функции, для которых достигается оценка (2), называют гипербент-функци-ями [1, 3]. Класс бент-функций инвариантен относительно невырожденной линейной замены переменных (см., например, [2]). В этом смысле основной результат данной работы демонстрирует отличие свойств бент- и гипербент-функций.

Рассмотрим вопрос о том, как влияет выбор базиса, в котором строится приведенное представление булевой функции, на его (представления) свойство «быть гипер-бент-функцией». Для d G 1, 2n — 2 через обозначим отображение на F2n такое, что

для любого x G F2n выполнено (x) = xd. Для различных d;, d" G 1, 2n — 2, каждое из которых взаимно просто с 2n — 1, отображения п^/ и п$/ задают различные подстановки на F2n. Кроме того, для любых d;, d" G 1, 2n — 2 выполнено п^// = п^// mod (2n—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 G 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^, е^,

/ (2) (2) (2) (2)\ ш ч

и ( е0 , е1 , е2 , е3 I векторного пространства (F 24)F , такие, что приведенное представление данной функции в первом базисе является, а во втором не является гипербент-функцией.

2) Для любого четного n > 4 существуют функции от n переменных, для каждой из которых можно найти два базиса векторного пространства (F2n )^ , таких, что приведенное представление функции в первом базисе является, а во втором не является гипербент-функцией.

ЛИТЕРАТУРА

1. Кузьмин А. С., Марков В. Т., Нечаев А. А., Шишков А. Б. Приближение булевых функций мономиальными // Дискретная математика. 2006. Т. 18. №1. С. 9-29.

2. Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МНЦМО, 2004. 470 с.

3. Youssef A. M., Gong G. Hyper-bent functions // Proceedings of Advances in Cryptology, EUR0CRYPT’2001. Lect. Notes in Comp. Sci. New York: Springer Verlag, 2001. V. 2045. P. 406-419.

УДК 519.7

СВОЙСТВА БЕНТ-ФУНКЦИЙ, НАХОДЯЩИХСЯ НА МИНИМАЛЬНОМ РАССТОЯНИИ ДРУГ ОТ ДРУГА

Н. А. Коломеец, А. В. Павлов, А. А. Левин

Здесь и далее пусть n — четное натуральное число. Обозначим:

— En — множество двоичных векторов длинны n;

— Fn — множество всех булевых функций от n переменных;

— нелинейность — расстояние Хэмминга до класса аффинных функций;

— бент-функции — булевы функции от четного числа переменных, обладающие максимальной нелинейностью;

— B — множество всех бент-функций от n переменных;

— D(f,g) = {x £ En I /(x) = g(x)} где /,# £ F„;

— / аффинна на D, если для некоторых w0 £ En, c £ E и для любого x £ D выпол-

няется /(x) = w0  x Ф c, где / £ Fn, D С En;

— d(A) — минимальное расстояние между двумя функциями в классе A С Fn;

— U — многообразие в En, т. е. U = x0 ф L, где L — подпространство в En, x0 £ En.

Имеет место нижняя оценка на расстояние между бент-функциями.

Теорема 1. Справедливо d(Bn) ^ 2n/2.

Следующая теорема дает критерий расположения функций на расстоянии 2n/2.

Теорема 2. Пусть /, g £ Fn, / — бент-функция, |D(/, g)| = 2n/2. Тогда g — бент-функция тогда и только тогда, когда множество D(/, g) — линейное многообразие размерности n/2 и / на нем аффинна.

Следствие 1. Минимальное расстояние в классе бент-функций равно 2n/2.

Определим следующие множества.