On Linear Representation, Complexity and Inversion of maps over finite fields
share
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 𝔽, 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 𝔽, 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 𝔽^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 𝔽^n under composition is also solved by extending the theory of linear representation of a single map.
READ FULL TEXT