|
Bulletin of Irkutsk State University. Series Mathematics, 2015, Volume 14, Pages 3–17
(Mi iigum239)
|
|
|
|
This article is cited in 6 scientific papers (total in 6 papers)
Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms
A. S. Baliuka, G. V. Yanushkovskyb a Irkutsk State University, 1, K. Marx st., Irkutsk, 664003
b Higher School of Economics, 20, Myasnitskaya st., Moscow, 101000
Abstract:
Polynomial representations of Boolean functions have been studied
well enough.
Recently, the interest to polynomial representations of functions over
finite fields and over finite rings is being increased.
There are a lot of difficulties in studying of the complexity
of these representations.
Only not equal upper and lower bounds has been obtained,
even for sagnificantly simple classes of polynomials.
This paper is about polarized polynomials over finite fields and their
generalizations: differentially and generically polarized polynomials.
Such a polynomial is a finite sum of products.
The difference between classes of polynomials is in constraints,
applied to the products.
Every polynomial represents an $n$-variable function over finite field.
A complexity of a polynomial is a number of nonzero summands in it.
Every function can be represented by several polynomials,
which are belongs to the same class.
A complexity of a function in a class of polynomials
is the minimal complexity of polynomials in the class,
which represent this function.
Previously, the upper bounds were known for arbitrary
$n$-variable function over primary finite field of order, greater than 2,
for the classes of polarized
and differentially polarized polynomials, as well as
for the class of generically polarized polynomials.
A representation of an $n$-ary function over finite field of order $q$
by a polarized polynomial or its generalization can be considered
as a Kroneker form.
This means, that the function, considered as a vector
in appropriate linear space,
is computed
by a linear transformation of a vector of coefficients of the polynomial,
where the matrix of this linear transformation is a Kroneker product
of $n$ nonsingular matrices with rank $q$.
This approach helped us to improve the upper bound for polarized
and differentially polarized polynomials
for the case of any finite field of odd order,
and to improve the upper bound for generically polarized polynomials
for the case of any
finite field of order, greater than 2.
Keywords:
finite field, polynomial, Kroneker form, complexity.
Citation:
A. S. Baliuk, G. V. Yanushkovsky, “Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms”, Bulletin of Irkutsk State University. Series Mathematics, 14 (2015), 3–17
Linking options:
https://www.mathnet.ru/eng/iigum239 https://www.mathnet.ru/eng/iigum/v14/p3
|
Statistics & downloads: |
Abstract page: | 225 | Full-text PDF : | 60 | References: | 51 |
|