Geodesic
On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials
The Bulletin of Irkutsk State University. Series Mathematics, Tome 17 (2016), pp. 378-45 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, polarized polynomial, complexity.
Mots-clés : polynomial 
@article{IIGUM_2016_17_a6,
     author = {A. S. Kazimirov and S. Yu. Reymerov},
     title = {On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {378--45},
     year = {2016},
     volume = {17},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2016_17_a6/}
}
TY  - JOUR
AU  - A. S. Kazimirov
AU  - S. Yu. Reymerov
TI  - On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2016
SP  - 378
EP  - 45
VL  - 17
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2016_17_a6/
LA  - ru
ID  - IIGUM_2016_17_a6
ER  - 
%0 Journal Article
%A A. S. Kazimirov
%A S. Yu. Reymerov
%T On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2016
%P 378-45
%V 17
%U http://geodesic.mathdoc.fr/item/IIGUM_2016_17_a6/
%G ru
%F IIGUM_2016_17_a6
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. The Bulletin of Irkutsk State University. Series Mathematics, Tome 17 (2016), pp. 378-45. http://geodesic.mathdoc.fr/item/IIGUM_2016_17_a6/

[1] Baliuk A. S., Yanushkovsky G. V., “Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms”, Izvestiya Irkustkogo gosudarstvennogo universiteta. Series Mathematics, 14 (2015), 3–17 (in Russian) | MR

[2] Baliuk A. S., Zinchenko A. S., “Lower bound on complexity of functions over finite field of order 4 in class of polarized polynomials”, Izvestiya Irkustkogo gosudarstvennogo universiteta. Series Mathematics, 16 (2016), 19–29 (in Russian) | MR | Zbl

[3] Graham R., Knuth D., Patashnik O., Concrete Mathmatics. A Foundation for Computer Science, Addison Wesley, 1994, 672 pp. | MR

[4] Zinchenko A. S., Panteleev V. I., “Polinomial operator representations of $k$-valued functions”, Diskretnyi Analiz i Issledovanie Operatsii. Series 1, 13:3 (2006), 13–26 (in Russian) | MR

[5] Lidl R., Niederreiter H., Finite Fields, Encyclopedia of Mathematics and its Applications, Cambridge University Press, England, 1984, 660 pp. | MR

[6] Markelov N. K., “A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials”, Moscow University Computational Mathematics and Cybernetics, 36:3 (2012), 150–154 | DOI | MR | MR | Zbl

[7] Peryazev N. A., “The complexity of Boolean functions in the class of polarized polynomial forms”, Algebra and Logic, 34:3 (1995), 323–326 (in Russian) | MR | Zbl

[8] Selezneva S. N., “On the complexity of representation of k-valued functions by generalised polarised polynomials”, Discrete Mathematics and Applications, 19:6 (2010), 653–663 | DOI | MR | Zbl

[9] Selezneva S. N., “On the complexity of representations of functions over multivalued logics by polarized polynomials”, Discrete Mathematics and Applications, 14:2 (2002), 48–53 (in Russian) | DOI | Zbl