On complexity of searching for periods of~functions given by polynomials over~a~prime~field

S. N. Selezneva

Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 56-73

Résumé

\hspace{-1pt}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\colon 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 polynomial-time algorithm with respect to the number of variables of the function. Bibliogr. 11.

Détail

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