On Complexity of Search for the Periods of Functions Given by Polynomials over a Prime Field

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.