An enhanced algorithm to search for low-degree annihilators for a Zhegalkin polynomial
Vladimir Valer'evich Baev · Discrete Mathematics and Applications · 2007
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.