|
|
Bulletin of Irkutsk State University. Series Mathematics, 2016, Volume 17, Pages 378–45
(Mi iigum271)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials
A. S. Kazimirov, S. Yu. Reymerov Irkutsk State University, 1, K. Marx st., Irkutsk, 664003
Abstract:
Recently, the interest to polynomial representations of functions over
finite fields and over finite rings is being increased. Complexity
of those representations is widely studied.
This paper introduces new upper bounds on complexity of discrete functions over particular finite fields in class of polarized polynomials. The results are state in the terms of matrix forms. A matrix form is representation of functions vector of values as a product of nonsingular matrix and a vector of coefficients. The complexity of matrix form of a special kind is equal to complexity of polarized polynomial for same function.
A complexity of a matrix form is a number of nonzero coefficients in its vector.
Every function can be represented by variety of matrix forms of the same class.
A complexity of a function in a class of matrix forms
is the minimal complexity of forms in the class representing this function.
This paper introduces new upper bounds on complexity of functions in class of polarized polynomials over fields of orders $2^k$ and $p^k$, $p$ is prime and $p \geqslant 3$.
Keywords:
finite field, polynomial, polarized polynomial, complexity.
Citation:
A. S. Kazimirov, S. Yu. Reymerov, “On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials”, Bulletin of Irkutsk State University. Series Mathematics, 17 (2016), 378–45
Linking options:
https://www.mathnet.ru/eng/iigum271 https://www.mathnet.ru/eng/iigum/v17/p378
|
|