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

We consider polynomials over a prime field of elements. With each polynomial under consideration, we associate the -valued function defined by the polynomial. A period of the -valued function is a tuple of elements in such that . In the paper, we propose an algorithm that, for an arbitrary prime and an arbitrary -valued function given by a polynomial over the field , finds a basis of the linear space of all periods of . Moreover, the complexity of the algorithm is , where is the degree of the polynomial defining . As a consequence, we show that for prime and each fixed number the problem of search for a basis of the linear space of all periods of a function given by a polynomial of degree at most can be solved by a polynomial-time algorithm with respect to the number of function variables. [ABSTRACT FROM AUTHOR]