On Linear Representation, Complexity and Inversion of maps over finite fields

arXiv2010.14601MaRDI QIDQ6505014FDOQ6505014

Ramachandran Anantharaman, Virendra R. Sule

Abstract: The paper primarily addressed the problem of linear representation, invertibility, and construction of the compositional inverse for non-linear maps over finite fields. Though there is vast literature available for the invertibility of polynomials and construction of inverses of permutation polynomials over $mathbbF$, this paper explores a completely new approach using the dual map defined through the Koopman operator. This helps define the linear representation of the non-linear map,, which helps translate the map's non-linear compositions to a linear algebraic framework. The linear representation, defined over the space of functions, naturally defines a notion of linear complexity for non-linear maps, which can be viewed as a measure of computational complexity associated with such maps. The framework of linear representation is then extended to parameter dependent maps over $mathbbF$, and the conditions on parametric invertibility of such maps are established, leading to a construction of a parametric inverse map (under composition). It is shown that the framework can be extended to multivariate maps over $mathbb{F}^n$, and the conditions are established for invertibility of such maps, and the inverse is constructed using the linear representation. Further, the problem of linear representation of a group generated by a finite set of permutation maps over $mathbb{F}^n$ under composition is also solved by extending the theory of linear representation of a single map.

This page was built for publication: On Linear Representation, Complexity and Inversion of maps over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505014)