Geodesic
Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1334-1340

Voir la notice de l'article provenant de la source Math-Net.Ru

Properties of the Boolean functions specified by the Zhegalkin polynomials in $n$ variables of degree not greater than $k$ are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology. In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations. Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does not reduce the asymptotic complexity of solving systems of linear Boolean equations. 
@article{ZVMMF_2010_50_7_a14,
     author = {K. N. Koryagin},
     title = {Level structure of {Zhegalkin} polynomials, properties of test sets, and an annihilator search algorithm},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1334--1340},
     publisher = {mathdoc},
     volume = {50},
     number = {7},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/}
}
TY  - JOUR
AU  - K. N. Koryagin
TI  - Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 1334
EP  - 1340
VL  - 50
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/
LA  - ru
ID  - ZVMMF_2010_50_7_a14
ER  - 
%0 Journal Article
%A K. N. Koryagin
%T Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 1334-1340
%V 50
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/
%G ru
%F ZVMMF_2010_50_7_a14
K. N. Koryagin. Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1334-1340. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a14/