Полином Жегалкина
англ. Zhegalkin polynomial
Единственное представление булевой функции в виде суммы по модулю 2 произведений переменных; линейность функции или её аффинность видны прямо по полиному.
Полином Жегалкина — запись булевой функции в виде суммы по модулю два произведений переменных: ; допускаются константы и мономы без степеней. Над полем из двух элементов сложение — это XOR, умножение — И, поэтому каждая функция от переменных раскладывается в такой полином, причём ровно одним способом. Это булев аналог многочлена: совпадение полиномов Жегалкина двух функций означает совпадение самих функций. Отправная точка построения — таблицы истинности из урока булева алгебра.
Ценность формы — в мгновенной диагностике структуры. Все мономы первой степени — функция линейна; есть константа — аффинна; наличие и старших произведений сразу говорит о нелинейности. Дизъюнкция и импликация в эту «чистую» компанию не попадают: их полиномы содержат произведение . Ручные приёмы — метод неопределённых коэффициентов (решение системы над ) и «треугольник»: последовательные XOR соседних значений по столбцам. Полином — главный инструмент при проверке функциональной полноты систем и задач класса постов.
Частые вопросы
Зачем нужен полином Жегалкина, если есть ДНФ?
Полином у функции один, а ДНФ много — значит, полином годится как канонический представитель: функции равны тогда и только тогда, когда равны их полиномы Жегалкина. Кроме того, алгебраическая форма подключает линейную алгебру над : коэффициенты ищутся решением системы. Степень полинома меряет нелинейность — в криптографии бент-функции специально строят с высокой степенью, чтобы усложнить атаки.
Как быстро построить полином Жегалкина вручную?
Метод треугольника: выписать столбец значений функции, затем многократно брать XOR соседних элементов, получая всё более короткие столбцы; первые элементы столбцов и есть коэффициенты при мономах в порядке возрастания. Второй путь — неопределённые коэффициенты: подставить наборы значений в общий полином и решать систему над . Для трёх-четырёх переменных оба способа занимают считанные минуты.