Geodesic
Multiaffine polynomials over a finite field
Diskretnaya Matematika, Tome 32 (2020) no. 3, pp. 85-97

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

We consider polynomials $f(x_1, \ldots, x_n)$ over a finite field that possess the following property: for some element $b$ of the field the set of solutions of the equation $f(x_1, \ldots, x_n) = b$ coincides with the set of solutions of some system of linear equations over this field. Such polynomials are said to be multiaffine with respect to the right-hand side $b$. We obtain the properties of multiaffine polynomials over a finite field. Then we show that checking the multiaffinity with respect to a given right-hand side may be done by an algorithm with polynomial (in terms of the number of variables and summands of the input polynomial) complexity. Besides that, we prove that in case of the positive decision a corresponding system of linear equations may be recovered with complexity which is also polynomial in terms of the same parameters.
Keywords: finite field, polynomial, multiaffinity, system of linear equations over a finite field, algorithm, complexity, polynomial algorithm. 
@article{DM_2020_32_3_a6,
     author = {S. N. Selezneva},
     title = {Multiaffine polynomials over a finite field},
     journal = {Diskretnaya Matematika},
     pages = {85--97},
     publisher = {mathdoc},
     volume = {32},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - Multiaffine polynomials over a finite field
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 85
EP  - 97
VL  - 32
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/
LA  - ru
ID  - DM_2020_32_3_a6
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T Multiaffine polynomials over a finite field
%J Diskretnaya Matematika
%D 2020
%P 85-97
%V 32
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/
%G ru
%F DM_2020_32_3_a6
S. N. Selezneva. Multiaffine polynomials over a finite field. Diskretnaya Matematika, Tome 32 (2020) no. 3, pp. 85-97. http://geodesic.mathdoc.fr/item/DM_2020_32_3_a6/