Volume 29, No 1, 2022, P. 56-73

UDC 519.712.3+512.622+510.52
S. N. Selezneva
On complexity of searching for periods of functions given by polynomials over a prime field

Abstract:
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 : 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 polynomialtime algorithm with respect to the number of variables of the function.

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

DOI: 10.33048/daio.2022.29.727

Svetlana N. Selezneva ¹
1. Lomonosov Moscow State University,
1 Leninskie Gory, 119991 Moscow, Russia
e-mail: selezn@cs.msu.ru

Received November 14, 2021
Revised November 14, 2021
Accepted November 26, 2021

References