Критерии сбалансированности функций

Исследуем сбалансированность функции ф е «при т<�п. Системой весовых характеристик системы функций [f_x{х_ь …, х»), …, f_m(x_v …, х")} называется множество чисел.

где (r_t, r_s) e X^s, {i_t, i₅} c {1, m}, 5 > 0. Система функций {f (x_u …,.

x_n)y —>^xn)} имеет нормальное весовое строение (н.в.с.), если JV*¹'" «*? =.

= ?'^/-s для любых {/ф i_s} с {1,т) и (r_t, r₅) g X⁵.

Теорема 7.2. Функция ф сбалансирована имеет н.в.с.

^ Ив определения весовых характеристик системы функций следует:

где (/*!, .-yj_m-_s} = {С …"/w}{ii, у, и слагаемые в правой части представимы в виде с помощью одинаковых перестановок верхнего и нижнего на боров индексов, (Ь_{, b_m) G Х^т. Если функция ф сбалансирована, то каждый элемент множества Х^т имеет относительно ф ровно kⁿ~^m прообразов. Тогда Лг!''" '"? = kⁿ~^m для любого набора (b_v •••" Ь_т) е Х^т и правая часть равенства (7.2).

есть сумма k^m~^s чисел, равных kⁿ~^m, т. е. равна kⁿ~^s. Значит, ф имеет н.в.с.

Если ф имеет н.в.с., то из определения весовых характеристик при s = т имеем, что N^X'"'^m = kⁿ~^m для любого набора (г_{, …, г_т) е Х^т_у т. е. каждый Ч '???' 'т

элемент множества Х^т имеет ровно kⁿ~^m прообразов относительно ф.? Следствие 1. т-булева функция ф сбалансирована для любого непустого подмножества {/_1?…, Q множества {1,…, т)

А Сбалансированная m-булева функция имеет н.в.с., в частности, =.

= 2ⁿ~^s. Поскольку ^{ДЛЯ т}~булевой функ ции ф, то (7.3) верно.

Пусть равенство (7.3) верно для m-булевой функции ф. Докажем равенство для любого непустого подмножества {ц₉ …, ij с {1, …, т) и любого.

(г^, Г₅) G Vy

Если (Г, …, r_s) = (1, 1), то (7.4) верно, оно совпадает с одним из ра венств (7.3). Пусть равенство (7.4) верно для любого подмножества {i_t,…, i_s} с (1, …, т) и любого набора (г_]; …, r_s) е V_s, имеющего менее d нулевых координат, <7 < s, s> 1.

Рассмотрим набор (r_t,…, r_s) из V_s, имеющий ровно d нулевых координат (без ущерба для общности считаем, что первые d координат нулевые и что {/, …, i_s) — {1, ._1!_х})₁_Для любых б.ф. / и V)/ верно: ||/ф | = ||v|/|| - ||/v|/||. В частности, для у = f₂-fdfd₊-fs ^и/ = /| имеем.

Отсюда, используя предположение индукции, получаем.

Иными словами, (7.4) верно для любого набора (г_ь …, г,) с d нулевыми координатами, и ф имеет н.в.с. ?

Доказанные критерии показывают, что распознавание сбалансированности функций в общем случае трудоемко уже при небольших п. Вместе с тем некоторые достаточные условия несбалансированности функций проверить несложно.

Следствие 2. Если функция ф е F_m « сбалансирована, то сбалансирована ее координатная функция /Х^х1> ^х»)>^{г =} 1″ —> ^т-

Л Сбалансированная функция имеет н.в.с., отсюда N'_a = к^п~^{ для любого яеХи любого i е {1,…, т}. Значит, все координатные функции сбалансированы. ?

При шифровании над элементами текста часто выполняются вычислительные операции в различных алгебраических структурах. Для функции ф: Р" —> Р^т, где Р — поле, справедлив следующий критерий сбалансированности^[1].

Теорема 7.3. Функция ф сбалансирована сбалансирована любая нетривиальная линейная комбинация ее координатных функций. О.

• [1] Лидл Р., андеррайтер Г. Конечные поля. Т. 2. М.: Мир, 1988.