Семейство координатных булевых функций

Любое отображение В : F?> -> F™ однозначно задается набором своих координатных булевых функций.

При этом В называют также векторной функцией.

Алгебраической степенью нелинейности отображения В называют величину.

Отображение (5.17) называется сбалансированным, или равновероятным, если при любом натуральном т и любом наборе У1,—-, Уше?₂ система уравнений.

имеет ровно 2^п~^т решений.

При п — гп сбалансированное отображение называется биективным, или обратимым (подстановочным, регулярным).

Определение 5.16. Множество булевых функций от п переменных /г,…, f_m, т ^ п называется ортогональной системой, если при любых Х[., Х_т € F'2 система уравнений

имеет ровно 2^п~^т решений в F?.

Таким образом, биективность отображения равносильна ортогональности множества его координатных функций. Один из критериев ортогональности получен в [3, том 2, стр. 464].

Утверждение 5.11. Система булевых функций {f,…, f_m}, in < п является ортогональной в том и только том случае, когда любая ненулевая линейная комбинация функций j приводит к рав

новероятной булевой функции.

Разбиение пространства FJf системой блоков

называется линеаризующим данное отображение В, если В является аффинным на каждом из множеств Х{. При этом число блоков разбиения t называется порядком линеаризующего разбиения.

В условиях линеаризующего разбиения (5.18) отображение В представимо в виде.

где A,…, At ~ аффинные отображения такие, что В (х) = АДж) при любом х 6 Xi, г = 1,…, t, a ipx_t следующие булевы функции:

Упражнение 5.8.1. Докажите, что при выполнении равенства (5.19) для степени нелинейности отображения В справедлива оценка

Упражнение 5.8.2. Докажите, что степень биективного отображения В : FJ> —" F? не превосходит величины п — 1.

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

Следующее утверждение устанавливает связь между степенями нелинейности прямого и обратного отображений.

Утверждение 5.12 (Колбин^[1]). Для степеней нелинейности отображений В и В~^г верны точные оценки

Важной характеристикой преобразования В является наименьшее натуральное число г, при котором преобразование аффинно (линейно). При этом соответствующее число г называется показателем аффинности (линейности) и обозначается соответственно г (А) и r (L). Каждый из этих показателей является делителем порядка циклической группы (В), порожденной биекцией В, т. е. делителем величины ord (F).

Утверждение 5.13. Если ord (F) —рпростое число, то

Доказательство данного утверждения может быть найдено в монографии В. Фомичева^[2].

Упражнение 5.8.3. Пусть В — биективное отображение на множестве Fj. Докажите, что если deg (jB) = п — 1, то deg (JB^_1) = п — 1.

• [1] См. Колбин С. Л. О некоторых свойствах взаимно обратных систем функцийр-значной логики // Дискретная маг., т. 6, вын. 2, 1994.
• [2] См. Фомичев В. М. Дискретная математика и криптология. Курс лекций /Под общей редакцией Н. Д. Подуфалова. — М.:ДИАЛОГ-МИФИ, 2003. — 400 с.