An enhanced algorithm to search for low-degree annihilators for a Zhegalkin polynomial

A Boolean function $g$ is said to be an annihilator of a Boolean function $f$ if $fg=0$. In some problems concerning finite automata, it is required to find non-zero annihilators of low algebraic degree for a function $f$.
In this paper we suggest Algorithm M2 which, given the Zhegalkin polynomial for a function $f$, yields a basis of the space of its annihilators of degree not exceeding $d$. Algorithm M2 is an enhancement of a previously known algorithm and allows in a series of cases to decrease calculations. The total complexity of Algorithm M2 is the same as for the previous algorithm.