|
Lower bound of the complexity of seven-valued functions in the class of polarized polynomials
A. S. Baliuk, A. S. Zinchenko Irkutsk State University, 1, K. Marx st., Irkutsk, 664003,
Russian Federation
Abstract:
One of the directions of the investigation of functions over finite fields
is the study of their representations, including polynomial ones.
In the area of polynomial representations of functions
the problem of estimating the complexity of such representations
can be highlighted.
The complexity of the polynomial, representing the function,
is the number of its non-zero terms.
Each function can be represented by several different polynomials
from the same class.
The complexity of a function in the class of polynomials
is the least possible complexity of a polynomial from this class,
representing the function.
The complexity of the given set of functions in the class of polynomials
is the maximal complexity of a function from the set
in this class of polynomials.
In the case of functions over a finite field of order 2 (Boolean functions),
exact values of the complexity of such representations are known
for many classes of polynomial forms.
But for functions over finite fields of order greater than two,
even in fairly simple classes of polynomials,
only mismatched upper and lower bounds of complexity have been found.
This paper is devoted to the study of the representation
of seven-valued functions by polarized polynomials.
The polynomials of this class have the form of a sum of a finite number
of products of a certain type.
For the case of Boolean and three-valued functions,
effective lower bounds for the complexity in the class of polarized polynomials
are known, as well as a weaker power estimate for functions over a finite field
of prime order.
In previous papers, the authors obtained effective lower bounds
for the complexity of functions over finite fields of order 4 and 5 in the class
of polarized polynomials.
In this paper an effective lower bound for the complexity of seven-valued
functions in the class of polarized polynomials has been obtained.
Keywords:
finite field, polarized polynomial, Kroneker form, complexity, lower bounds.
Citation:
A. S. Baliuk, A. S. Zinchenko, “Lower bound of the complexity of seven-valued functions in the class of polarized polynomials”, Bulletin of Irkutsk State University. Series Mathematics, 22 (2017), 18–30
Linking options:
https://www.mathnet.ru/eng/iigum320 https://www.mathnet.ru/eng/iigum/v22/p18
|
Statistics & downloads: |
Abstract page: | 169 | Full-text PDF : | 60 | References: | 29 |
|