On complexity of searching for periods of functions given by polynomials over a prime field

S. N. Selezneva

Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 56-73

Résumé

\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.

Détail

Keywords: $p$-valued function (function of $p$-valued logic), finite field, prime field, polynomial over a field, periodicity, algorithm, complexity.

Bibliographie

[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