Полиномиальные алгоритмы вычисления локальных аффинностей квадратичных булевых функций

Аффинная нормальная форма позволяет рассматривать произвольную булеву функцию на определенных плоскостях (так называемых локальных аффинностях) как аффинную. Данное представление — по сути, аффинная аппроксимация — булевых функций может помочь в решении систем нелинейных уравнений над полем из двух элементов. Задача решения таких систем (специального вида), среди прочего, используется в ряде методов синтеза и анализа средств обеспечения информационной безопасности. В статье описывается способ нахождения локальных аффинностей для квадратичных булевых функций, основанный на теореме Диксона. Тем самым решается задача построения аффинных нормальных форм для таких функций. Кроме того, обсуждаются вопросы эффективности подобных алгоритмов. Основная цель данной статьи — подготовить базу для готовящейся к публикации работы, предлагающей метод решения систем квадратичных булевых уравнений с помощью «аппроксимирования» соответствующих функций их аффинными нормальными формами.