Geodesic
On complexity of searching for periods of~functions given by polynomials over~a~prime~field
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 56-73.

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

\hspace{-1pt}We consider polynomials over the prime field $F_p = (E_p; +, \cdot)$ of $p$ elements. With each polynomial $f(x_1, \ldots, x_n)$ under consideration, we associate a $p$-valued function $f\colon E_p^n \to E_p$ that the polynomial defines. A period of a $p$-valued function $f(x_1, \ldots, x_n)$ is a tuple $a = (a_1, \ldots, a_n)$ of elements from $E_p$ such that $f(x_1+a_1, \ldots, x_n+a_n) = f(x_1, \ldots, x_n).$ In the paper, we propose an algorithm that, for $p$ prime and an arbitrary $p$-valued function $f(x_1, \ldots, x_n)$ given by a polynomial over the field $F_p,$ finds a basis of the linear space of all periods of $f.$ Moreover, the complexity of the algorithm is equal to $n^{O(d)},$ where $d$ is the degree of the polynomial that defines $f.$ As a consequence, we show that for $p$ prime and each fixed number $d$ the problem of searching for a basis of the linear space of all periods of a function $f$ given by a polynomial of the degree at most $d$ can be solved by a polynomial-time algorithm with respect to the number of variables of the function. Bibliogr. 11.
Keywords: $p$-valued function (function of $p$-valued logic), finite field, prime field, polynomial over a field, periodicity, algorithm, complexity. 
@article{DA_2022_29_1_a4,
     author = {S. N. Selezneva},
     title = {On complexity of searching for periods of~functions given by polynomials over~a~prime~field},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {56--73},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_1_a4/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On complexity of searching for periods of~functions given by polynomials over~a~prime~field
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 56
EP  - 73
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_1_a4/
LA  - ru
ID  - DA_2022_29_1_a4
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On complexity of searching for periods of~functions given by polynomials over~a~prime~field
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 56-73
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_1_a4/
%G ru
%F DA_2022_29_1_a4
S. N. Selezneva. On complexity of searching for periods of~functions given by polynomials over~a~prime~field. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 56-73. http://geodesic.mathdoc.fr/item/DA_2022_29_1_a4/

[1] O. A. Logachyov, A. A. Sal'nikov, S. V. Smyshlyaev, V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology, MTsNMO, M., 2012 (Russian)

[2] Dawson E., Wu C.-K., “On the linear structure of symmetric Boolean functions”, Australas. J. Comb., 16 (1997), 239–243

[3] V. K. Leont'ev, “Certain problems associated with Boolean polynomials”, Comput. Math. Math. Phys., 39:6 (1999), 1006–1015

[4] S. N. Selezneva, “On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials”, Discrete Math. Appl., 7:6 (1997), 565–572

[5] S. N. Selezneva, “A polynomial algorithm for the recognition of belonging a function of $k$-valued logic realized by a polynomial to precomplete classes of self-dual functions”, Discrete Math. Appl., 8:5 (1998), 483–492

[6] Grigoriev D. Yu., “Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines”, Theor. Comput. Sci., 180:1–2 (1997), 217–228

[7] D. Yu. Grigoriev, “Testing the shift-equivalence of polynomials using quantum machines”, J. Math. Sci., 82:1 (1996), 3184–3193

[8] S. N. Selezneva, “On searching periods of Zhegalkin polynomials”, Diskretn. Mat., 33:3 (2021), 107–120 (Russian)

[9] R. Lidl, H. Niederreiter, Finite Fields, Camb. Univ. Press, Cambridge, 1985

[10] S. V. Yablonskii, Introduction to Discrete Mathematics, Vysshaya Shkola, M., 2001 (Russian)

[11] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979