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

The Bulletin of Irkutsk State University. Series Mathematics, Tome 17 (2016), pp. 378-45

Résumé

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$.

Détail

Keywords: finite field, polarized polynomial, complexity.
Mots-clés : polynomial