On complexity of search for the periods of functions given by polynomials over a prime fieldстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 27 июля 2022 г.
Аннотация:We consider polynomials over a prime field Fp = (Ep; +, ·) of p elements. With each polynomial f(x1, ..., xn) under consideration, we associate the p-valued function f : Ep^n \to Ep defined by the polynomial. A period of the p-valued function f(x1, ..., xn) is a tuple a = (a1, ..., an) of elements in Ep such that f(x1+a 1, ..., xn+an) = f(x1, ..., xn). In the paper, we propose an algorithm that, for an arbitrary prime p and an arbitrary p-valued function f(x1, ..., xn) given by a polynomial over the field Fp, 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.