Материалы что дал Мухачев / Материалы что дал Мухачев / Білети_коротки_відповіді / Білети_відпові_БСДМ / Mg_Vidp44

44. Максимально нелінійні булеві функції. Які булеві функції є максимально нелінійні при парному ?

Функція називається максимально нелінійною, якщо значення нелінійності досягає максимально можливого значення для булевих функцій від змінних ( може бути непарним). Актуальною задачею залишається опис класу функцій для яких , у залежності від , зокрема, при .

Відомо, що для довільної булевої функції , , а її нелінійність виражається через коефіціенти Уолша Адамара наступним чином.

Виявляється, що існують булеві функції з нелінійністю , для яких всі коефіцієнти Уолша-Адамара досягають нижньої границі і дорівнюють , наприклад, .

Такі функції називаються бент-функціями. Вони є максимально нелінійними при . Для них .