|
Bulletin of Irkutsk State University. Series Mathematics, 2014, Volume 10, Pages 3–12
(Mi iigum205)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
On upper bound of the complexity of quasi polynomial representations of functions over finite fields
A. S. Baliuk Irkutsk State University, 1, K. Marx st., Irkutsk, 664003
Abstract:
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$.
Keywords:
finite field, polynomial, quasi polynomial, complexity.
Citation:
A. S. Baliuk, “On upper bound of the complexity of quasi polynomial representations of functions over finite fields”, Bulletin of Irkutsk State University. Series Mathematics, 10 (2014), 3–12
Linking options:
https://www.mathnet.ru/eng/iigum205 https://www.mathnet.ru/eng/iigum/v10/p3
|
Statistics & downloads: |
Abstract page: | 149 | Full-text PDF : | 45 | References: | 34 |
|