Affine Annihilator Finding Algorithm for Boolean Function
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 B...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
MGTU im. N.È. Baumana
2021-05-01
|
| Series: | Matematika i Matematičeskoe Modelirovanie |
| Subjects: | |
| Online Access: | https://www.mathmelpub.ru/jour/article/view/255 |
| _version_ | 1811232480883113984 |
|---|---|
| author | A. S. Zelenetsky P. G. Klyucharev |
| author_facet | A. S. Zelenetsky P. G. Klyucharev |
| author_sort | A. S. Zelenetsky |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T11:03:30Z |
| format | Article |
| id | doaj.art-6b58c3d4605c405380c57d62db27540a |
| institution | Directory Open Access Journal |
| issn | 2412-5911 |
| language | Russian |
| last_indexed | 2024-04-12T11:03:30Z |
| publishDate | 2021-05-01 |
| publisher | MGTU im. N.È. Baumana |
| record_format | Article |
| series | Matematika i Matematičeskoe Modelirovanie |
| spelling | doaj.art-6b58c3d4605c405380c57d62db27540a2022-12-22T03:35:52ZrusMGTU im. N.È. BaumanaMatematika i Matematičeskoe Modelirovanie2412-59112021-05-0101132610.24108/mathm.0121.0000255158Affine Annihilator Finding Algorithm for Boolean FunctionA. S. Zelenetsky0P. G. Klyucharev1Bauman Moscow State Technical University, MoscowBauman Moscow State Technical University, MoscowSo 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.https://www.mathmelpub.ru/jour/article/view/255boolean functionsannihilatoraffine functions |
| spellingShingle | A. S. Zelenetsky P. G. Klyucharev Affine Annihilator Finding Algorithm for Boolean Function Matematika i Matematičeskoe Modelirovanie boolean functions annihilator affine functions |
| title | Affine Annihilator Finding Algorithm for Boolean Function |
| title_full | Affine Annihilator Finding Algorithm for Boolean Function |
| title_fullStr | Affine Annihilator Finding Algorithm for Boolean Function |
| title_full_unstemmed | Affine Annihilator Finding Algorithm for Boolean Function |
| title_short | Affine Annihilator Finding Algorithm for Boolean Function |
| title_sort | affine annihilator finding algorithm for boolean function |
| topic | boolean functions annihilator affine functions |
| url | https://www.mathmelpub.ru/jour/article/view/255 |
| work_keys_str_mv | AT aszelenetsky affineannihilatorfindingalgorithmforbooleanfunction AT pgklyucharev affineannihilatorfindingalgorithmforbooleanfunction |