1. Affine Annihilator Finding Algorithm for Boolean Function
- Author
-
A. S. Zelenetsky and P. G. Klyucharev
- Subjects
Discrete mathematics ,0209 industrial biotechnology ,Degree (graph theory) ,affine functions ,010102 general mathematics ,boolean functions ,02 engineering and technology ,01 natural sciences ,Annihilator ,Identity (mathematics) ,020901 industrial engineering & automation ,annihilator ,QA1-939 ,Affine transformation ,0101 mathematics ,Representation (mathematics) ,Boolean function ,Equivalence (measure theory) ,Mathematics ,Variable (mathematics) - Abstract
So far, there are no efficient algorithms to solve a problem of finding the low degree annihilators for arbitrary Boolean function. In the paper we present a new algorithm to find affine annihilators for an arbitrary Boolean function. We start with considering the identity fg ≡ 0 or the arbitrary Boolean function f and its possible affine annihilator g. We use a special representation of the Boolean function in sum of its sub-functions to reduce degrees of considering functions in previous identity. As a result, we establish equivalence between the identity fg ≡ 0 for Boolean functions of n variables and the system of Boolean equations of n-1 variable.An algorithm for finding the affine annihilators for the arbitrary Boolean function f must find all the affine functions g so that fg ≡ 0. Our algorithm is based on reducing the problem of finding the affine annihilators for the Boolean function f of n to the similar problem for its sub-functions of n-1 variable. The presented algorithm has the following advantages:An input function can be presented in different ways;Output can be also presented in different ways;The algorithm can be effectively parallelized.It should be noted that the result we have obtained is not final and highlights some development directions: first, to study the impact of its input and output on the efficiency of the algorithm of various representations and, second, to use our idea of constructing the algorithm for development of algorithms, which allow finding the 2nd, 3rd, etc. degree annihilators for a specified Boolean function.
- Published
- 2021