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/

[1] Gorshkov S. P., “O slozhnosti raspoznavaniya multiaffinnosti, biyunktivnosti, slaboi polozhitelnosti i slaboi otritsatelnosti”, Obozr. promyshl. prikl. matem., 4:2 (1997), 216–237

[2] Selezneva S. N., “O multiaffinnykh mnogochlenakh nad konechnym polem”, Diskretnaya matematika, 32:3 (2020), 85–97 | DOI

[3] Selezneva S. N., O proverke multiaffinnosti funktsii algebry logiki po ikh mnogochlenam Zhegalkina, 2022, no. 1, 42–49 | MR | Zbl

[4] Lidl R., Niderraiter G., Konechnye polya, Mir, M., 1988, 430 pp.

[5] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, M., 2001, 384 pp.

[6] Yablonskii S. V., Gavrilov G. P., Nabebin A. A., Predpolnye klassy v mnogoznachnykh logikakh, Izd-vo MEI, M., 1997, 144 pp. | MR

[7] Tyrtyshnikov E. E., Osnovy algebry, Fizmatlit, M., 2017, 464 pp.

[8] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp.