Уровневая структура полиномов Жегалкина, свойства тестовых множеств и алгоритм поиска аннигиляторов

В начале статьи исследуются свойства булевых функций, заданных полиномами Жегалкина степени не выше $k$ от $n$ переменных с точки зрения закономерности размещения их единичных (нулевых) точек на единичном кубе. Далее рассматривается вопрос о свойствах тестовых множеств для полиномов Жегалкина, где основное значение имеют тупиковые тестовые множества. В конце статьи описывается детерминированный (не вероятностный) алгоритм для поиска всех аннулирующих многочленов (аннигиляторов) для заданного полинома, в том числе поиск аннигиляторов минимальной степени, имеющих приложение в криптологии. В известных алгоритмах поиска аннигиляторов задача сводится к решению систем линейных булевых уравнений. Понижение размерности этих систем уменьшает алгоритмическую сложность решения задачи. Предложенный алгоритм позволяет достичь этой цели, но не решает вопроса улучшения асимптотической сложности решения этих систем. Библ. 6.