RUS  ENG
Full version
JOURNALS // Bulletin of Irkutsk State University. Series Mathematics // Archive

Bulletin of Irkutsk State University. Series Mathematics, 2016 Volume 17, Pages 378–45 (Mi iigum271)

This article is cited 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.

UDC: 519.715

MSC: 68Q17



© Steklov Math. Inst. of RAS, 2024