EN|RU

Volume 29, No 1, 2022, P. 56-73

UDC 519.712.3+512.622+510.52
S. N. Selezneva
On complexity of searching for periods of functions given by polynomials over a prime field

Abstract:
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 : 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 polynomialtime algorithm with respect to the number of variables of the function.

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

DOI: 10.33048/daio.2022.29.727

Svetlana N. Selezneva 1
1. Lomonosov Moscow State University,
1 Leninskie Gory, 119991 Moscow, Russia
e-mail: selezn@cs.msu.ru

Received November 14, 2021
Revised November 14, 2021
Accepted November 26, 2021

References

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

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

[3] V. K. Leont’ev, Certain problems associated with Boolean polynomials, Zh. Vychisl. Mat. Mat. Fiz. 39 (6), 1045–1054 (1999) [Russian] [Comput. Math. Math. Phys. 39 (6), 1006–1015 (1999)].

[4] S. N. Selezneva, On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials, Diskretn. Mat. 9 (4), 24–31 (1997) [Russian] [Discrete Math. Appl. 7 (6), 565–572 (1997)].

[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 selfdual functions, Diskretn. Mat. 10 (3), 64–72 (1998) [Russian] [Discrete Math. Appl. 8 (5), 483–492 (1998)].

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

[7] D. Yu. Grigoriev, Testing the shift-equivalence of polynomials using quantum machines, Itogi Nauki Tekh., Ser. Sovrem. Mat. Pril. 34, 98–116 (1996) [Russian] [J. Math. Sci 82 (1), 3184–3193 (1996)].

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

[9] R. Lidl and H. Niederreiter, Finite Fields (Camb. Univ. Press, Cambridge, 1985; Mir, Moscow, 1988 [Russian]).

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

[11] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
 © Sobolev Institute of Mathematics, 2015