On upper bound of the complexity of quasi polynomial representations of functions over finite fields

A. S. Baliuk

The Bulletin of Irkutsk State University. Series Mathematics, Tome 10 (2014), pp. 3-12

Résumé

Representations of functions over finite fields, including polynomial representations, are being actively investigated. The complexity of such representations is one of main directions of research. This paper is about quasi polynomial complexity of functions over finite fields. Quasi polynomial can be considered as a regular polynomial with the following transformation: every occurence $x_i^0, \dots, x_i^{k-1}$ of selected variable $x_i$ is replaced by a function from a set $\{g_0(x_i), \dots, g_{k-1}(x_i)\}$ of linearly independent unary functions. The number of terms, the number of occurences of variables, or the degree of a polynomial are usually used as a measure of complexity. In the case of quasi polynomials one can use the number of terms as a natural measure of complexity, while further generalization are required for the number of occurences of variables and the degree of a polynomial. In this paper the number of terms is used as a measure of complexity. Previously, the upper bound of such a complexity was known for polynomials over finite fields of prime order. Namely, the quasi polynomial complexity of $n$-ary function over finite field of prime order $k$ is at most $\frac{k}{k+1}k^n$. In this paper an upper bound for the quasi polynomial complexity of functions over finite fields of arbitrary order $q$ has been obtained, which significantly improves previously known upper bound for modulo prime quasi polynomials, if $q \geqslant 3$. Namely, the quasi polynomial complexity of any $n$-ary function over finite field of order $q$ is at most $ \frac{q-1}{q-q^{1-q}}q^n$.

Détail

Keywords: finite field, complexity.
Mots-clés : polynomial, quasi polynomial