Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина

Булева функция $g$ называется аннигилятором булевой функции $f$, если $fg=0$. В некоторых задачах анализа конечных автоматов требуется найти для функции $f$ ненулевые аннигиляторы низкой алгебраической степени.
В статье представлен алгоритм M2, вычисляющий для многочлена Жегалкина функции $f$ базис пространства ее аннигиляторов степени, не превосходящей $d$. Алгоритм M2 является усовершенствованием разработанного ранее алгоритма и позволяет в ряде случаев сократить вычисления. При этом общая оценка сложности алгоритма M2 та же, что и для прежнего алгоритма.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 07-01-00154.