Взаимосвязь коэффициентов полинома над полем и веса булевой функции | ПДМ. 2014. № 4(26).

Взаимосвязь коэффициентов полинома над полем и веса булевой функции

Работа посвящена изучению зависимости коэффициентов многочлена одного переменного, задающего над полем из 2 элементов булеву функцию, от веса исследуемой функции. Получены точные формулы зависимости коэффициентов многочлена от первых двух коэффициентов веса в двоичном представлении и ограничения на линейные многообразия функций из рассматриваемых специальных классов.

Relationship between the coefficients of polynomials over GF(2 ) and weights of Boolean functions represented by them.pdf Введение В 70-х годах прошлого века был введён класс функций, находящихся на наибольшем расстоянии, с точки зрения метрики Хемминга, от класса аффинных функций; такие функции названы О. С. Ротхаузом бент-функциями [1]. В дальнейшем в работе [2] А. Йоссефом и Г. Гонгом построен класс функций, которые находятся на наибольшем расстоянии от мономиальных функций - класс гипер-бент-функций. Несмотря на многочисленные исследования в этой области, пока не получено полного описания данных классов функций. Этим объясняется актуальность изучения свойств бент-функций и гипер-бент-функций и поиска новых методов их анализа. При изложении результатов удобно использовать представление булевых функций от n переменных в виде многочленов над полем GF(2n). Пусть P - GF(2) - поле из двух элементов, Q - GF(2n) -расширение поля P степени n. Булевы функции f (x0, x1,... , xn-1) от n переменных можно рассматривать как функции вида F : Q ^ P. Для простоты будем считать, что f (0, 0,..., 0) - 0. Обозначим через е0, е1,..., £П-1 базис поля GF(2n) как векторного пространства над полем GF(2), а через ш0,ш1,...,шП-1 - базис поля GF(2n) над полем GF(2), двойственный к базису е0, е1,..., еП-1, т. е. П/ Г I, если j - k, 1 0, если j - k, n- 1 где trn(x) - Е x2 -функция «след» из поля GF(2n) в поле GF(2). 1 k=0 Тогда для любого набора булевых величин x0,x1,... ,xn-1 однозначно определён элемент x G GF(2n): n- 1 x x2^2. k=0 При этом, в силу двойственности базисов, справедливо соотношение xk - trn(^2x). Таким образом, для булевой функции f (x0,x1,... ,xn-1) имеет место равенство f (xo,x1,... ,xn-1) - f (trn(^ox), tr^^x),... , trn(^n-1x)), задающее эту функцию в виде полинома над полем GF(2n) в базисе £0, £1,... ,£n-1. Обозначим F(x) = f (trn(w0x), trn(^x),... , trn(wn-1x)). Так как функция F представляется в виде многочлена над полем, то 2n-1 F(x) = E ckxk, x G Q. (1) k=1 Здесь коэффициенты ck принадлежат полю GF(2n). Заметим, что c0 = 0, так как F(0) = 0, поэтому в формуле (1) сумма начинается c k =1. Поскольку многочлен F(x) принимает только два значения 0 или 1, то он может быть представлен в виде F (x) = tr^(x)), где Ф^) -некоторый полином над полем GF(2n). В работе [3] показано, что существует представление функции F(x), в котором многочлен Ф^) имеет вид ф^) = Е 4£kxk, ck G Qk, k G M. (2) keM Здесь M - набор минимальных представителей всех различных циклотомических классов по модулю 2n - 1 [4, с. 108], Qk = GF(2r), где значение r определяется условия- ( 2n - 1 | 1 ми r = mm < t : t> 0,---|(24 - 1U , а £k - фиксированный элемент поля GF(2n), (2n - 1, k) след которого в подполе GF(2r) равен 1. Замечание 1. Из формул (1) и (2), а также из формулы F(x) = trn^(x)) следует, что ck = c'k£k, если k G M. Отсюда следует также, что если c'k£k = 0, то ct = 0 для всех таких t, что t и k лежат в одном циклотомическом классе. 1. Зависимости коэффициентов в представлении в виде многочлена над конечным полем от веса булевой функции Рассмотрим задачу установления зависимости коэффициентов многочлена F(x) от параметров двоичного разложения веса самой функции ||F|| = n0 + 2n1 + 4n2 + • • • , где n G {0,1}. Под весом понимается сумма значений функции по всем аргументам, т.е. ||F|| = Е F(x), где суммирование ведётся в действительной области. xeQ Утверждение 1. Коэффициент c2n-1 = 0 тогда и только тогда, когда n0 = 0. Доказательство. Очевидно, что n0 = Е F(x), где суммирование ведётся в поxeQ ле Q характеристики 2. Тогда 2n-1 n0 = Е Е ck xk. xeQ k=1 Любой обратимый элемент x поля Q можно представить в виде в4 для подходящего t G {0,1,..., 2n - 2}, где в - примитивный элемент поля Q. Учитывая, что c0 = 0, получаем 2n-2 2n-1 n0 = Е Е ck(e4)k. t=0 k=1 Поменяем порядок суммирования и выделим слагаемое, соответствующее k = 2n - 1: 2n-2 2n-2 2n -2 n0 = E ck E (ek)4 + c2n-1 E (в2"-1)4. k=1 t=0 t=0 Порядок 9 равен 2n - I, следовательно, вторая сумма при коэффициенте C2n-1 есть суммирование единиц 2n - I раз; значит, она равна 1. Теперь, применяя формулу для вычисления суммы геометрической прогрессии, получаем равенство 2"-2 92(2n-1) _ I По - E C2-----+ C2n-1 - C2n-1. 2=1 9 - I Таким образом, имеем, что n0 - 0 тогда и только тогда, когда с2и-1 - 0. ■ n Лемма 1 [5]. Пусть a G {0, I}, i G {I, 2,..., n} и E a - k - n0 + 2n1 + 4n2 + ..., i=1 где суммирование ведётся в области целых чисел. Тогда n1 - E ai(mod 2). Теорема 1. Пусть F : Q ^ P, F(0) - 0 и ||F|| - n0 + 2n1 + 4n2 + ... Тогда 2n-1-1 П1 - C2„-1 + E C2C2"-1-2. (3) =1 Доказательство. Зафиксируем примитивный элемент 9 поля Q и аналогично тому, как было сделано в лемме 1, представим элементы поля Q через элемент 9. Пусть x и y - элементы поля Q, x - 9 2, y - 91, где k, l - натуральные числа. Будем считать, что x < y тогда и только тогда, когда k < l. Согласно лемме 1, имеем /2"-1 2"-1 \ П1 - Е F(x1)F(x2) - Е ( Е C2x 2 Е С4 ) . xi,x2€Q : xi

Ключевые слова

булева функция, бент-функция, многочлен над полем, вес функции, подпространство, многообразия, Boolean function, bent function, polynomial over a field, vector space, weight of function, subspaces

Авторы

ФИООрганизацияДополнительноE-mail
Ноздрунов Владислав ИгоревичЛаборатория ТВП, г. Москвасотрудник лабораторииvlad_vin@mail.ru
Кузьмин Алексей СергеевичЛаборатория ТВП, г. Москвадоктор физико-математических наук, профессор
Всего: 2

Ссылки

Rothaus O.S. On bent functions // J. Combinatorial Theory. 1976. V. 20(A). P. 300-305.
YoussefA. and Gong G. Hyper-bent functions // LNCS. 2001. V.2045. P. 406-419.
Логачев О. А., Сальников А. А., ЯщенкоВ. В. О свойствах сумм Вейля на конечных полях и конечных абелевых группах // Дискретная математика. 1999. Т. 11. №2. С. 66-85.
Мак-Вильямс Ф.Дж., Слоэн Н.Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
Rueppel R. A. Analysis and Design of Stream Ciphers. Berlin: Springer, 1986. 244 p.
Логачев О. А., Сальников А. А., ЯщенкоВ. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004.
Кузьмин А. С., Марков В. Т., Нечаев А. А., Шишков А. Б. Приближение булевых функций мономиальными // Дискретная математика. 2006. Т. 18. №1. С. 9-29.
 Взаимосвязь коэффициентов полинома над полем и веса булевой функции | ПДМ. 2014. № 4(26).

Взаимосвязь коэффициентов полинома над полем и веса булевой функции | ПДМ. 2014. № 4(26).