On Complexity of Search for the Periods of Functions Given by Polynomials over a Prime Field
Светлана Николаевна Селезнева · Journal of Applied and Industrial Mathematics · 2022
We consider polynomials over a prime field $$ F_p = (E_p; +, \cdot ) $$ of $$ p $$ elements. With each polynomial $$ f(x_1, \ldots , x_n) $$ under consideration, we associate the $$ p $$ -valued function $$ f\colon E_p^n \to E_p $$ defined by the polynomial. A period of the $$ p $$ -valued function $$ f(x_1, \ldots , x_n) $$ is a tuple $$ a = (a_1, \ldots , a_n) $$ of elements in $$ 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 an arbitrary prime $$ p $$ 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 $$ n^{O(d)} $$ , where $$ d $$ is the degree of the polynomial defining $$ f $$ . As a consequence, we show that for prime $$ p $$ and each fixed number $$ d $$ the problem of search for a basis of the linear space of all periods of a function $$ f $$ given by a polynomial of degree at most $$ d $$ can be solved by a polynomial-time algorithm with respect to the number of function variables.