Geodesic
Deciding multiaffinity of polynomials over a finite field
Diskretnaya Matematika, Tome 35 (2023) no. 2, pp. 109-124

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

We consider polynomials $f(x_1, \dots, x_n)$ over a finite filed that satisfy the following condition: the set of solutions of the equation $f(x_1, \dots, x_n) = b$, where $b$ is some element of the field, coincides with the set of solutions of some system of linear equations over this field. Such polynomials are said to be multiaffine with the right-hand side $b$ (or with respect to $b$). We describe a number of properties of multiaffine polynomials. Then on the basis of these properties we propose a polynomial algorithm that takes a polynomial over a finite field and an element of the field as an input and decides whether the polynomial is multiaffine with respect to this element. In case of the positive answer the algorithm also outputs a system of linear equations that corresponds to this polynomial. The complexity of the proposed algorithm is the smallest in comparison with other known algorithms that solve this problem.
Keywords: finite field, polynomial, multiaffinity, system of linear equations over a finite field, algorithm, complexity, polynomial algorithm. 
@article{DM_2023_35_2_a6,
     author = {S. N. Selezneva},
     title = {Deciding multiaffinity of polynomials over a finite field},
     journal = {Diskretnaya Matematika},
     pages = {109--124},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2023_35_2_a6/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - Deciding multiaffinity of polynomials over a finite field
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 109
EP  - 124
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2023_35_2_a6/
LA  - ru
ID  - DM_2023_35_2_a6
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T Deciding multiaffinity of polynomials over a finite field
%J Diskretnaya Matematika
%D 2023
%P 109-124
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2023_35_2_a6/
%G ru
%F DM_2023_35_2_a6
S. N. Selezneva. Deciding multiaffinity of polynomials over a finite field. Diskretnaya Matematika, Tome 35 (2023) no. 2, pp. 109-124. http://geodesic.mathdoc.fr/item/DM_2023_35_2_a6/