Finding periods of Zhegalkin polynomials
Светлана Николаевна Селезнева · Discrete Mathematics and Applications · 2022
Abstract A period of a Boolean function f ( x 1 , …, x n ) is a binary n -tuple a = ( a 1 , …, a n ) that satisfies the identity f ( x 1 + a 1 , …, x n + a n ) = f ( x 1 , …, x n ). A Boolean function is periodic if it admits a nonzero period. We propose an algorithm that takes the Zhegalkin polynomial of a Boolean function f ( x 1 , …, x n ) as the input and finds a basis of the space of all periods of f ( x 1 , …, x n ). The complexity of this algorithm is n O ( d ) , where d is the degree of the function f . As a corollary we show that a basis of the space of all periods of a Boolean function specified by the Zhegalkin polynomial of a bounded degree may be found with complexity which is polynomial in the number of variables.