On Linear Representation, Complexity and Inversion of maps over finite fields
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910396631220224 |
|---|---|
| author | Anantharaman, Ramachandran Sule, Virendra |
| author_facet | Anantharaman, Ramachandran Sule, Virendra |
| contents | This paper defines a linear representation for nonlinear maps $F:\mathbb{F}^n\rightarrow\mathbb{F}^n$ where $\mathbb{F}$ is a finite field, in terms of matrices over $\mathbb{F}$. This linear representation of the map $F$ associates a unique number $N$ and a unique matrix $M$ in $\mathbb{F}^{N\times N}$, called the Linear Complexity and the Linear Representation of $F$ respectively, and shows that the compositional powers $F^{(k)}$ are represented by matrix powers $M^k$. It is shown that for a permutation map $F$ with representation $M$, the inverse map has the linear representation $M^{-1}$. This framework of representation is extended to a parameterized family of maps $F_λ(x): \mathbb{F} \to \mathbb{F}$, defined in terms of a parameter $λ\in \mathbb{F}$, leading to the definition of an analogous linear complexity of the map $F_λ(x)$, and a parameter-dependent matrix representation $M_λ$ defined over the univariate polynomial ring $\mathbb{F}[λ]$. Such a representation leads to the construction of a parametric inverse of such maps where the condition for invertibility is expressed through the unimodularity of this matrix representation $M_λ$. Apart from computing the compositional inverses of permutation polynomials, this linear representation is also used to compute the cycle structures of the permutation map. Lastly, this representation is extended to a representation of the cyclic group generated by a permutation map $F$, and to the group generated by a finite number of permutation maps over $\mathbb{F}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2010_14601 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | On Linear Representation, Complexity and Inversion of maps over finite fields Anantharaman, Ramachandran Sule, Virendra Symbolic Computation Discrete Mathematics Representation Theory This paper defines a linear representation for nonlinear maps $F:\mathbb{F}^n\rightarrow\mathbb{F}^n$ where $\mathbb{F}$ is a finite field, in terms of matrices over $\mathbb{F}$. This linear representation of the map $F$ associates a unique number $N$ and a unique matrix $M$ in $\mathbb{F}^{N\times N}$, called the Linear Complexity and the Linear Representation of $F$ respectively, and shows that the compositional powers $F^{(k)}$ are represented by matrix powers $M^k$. It is shown that for a permutation map $F$ with representation $M$, the inverse map has the linear representation $M^{-1}$. This framework of representation is extended to a parameterized family of maps $F_λ(x): \mathbb{F} \to \mathbb{F}$, defined in terms of a parameter $λ\in \mathbb{F}$, leading to the definition of an analogous linear complexity of the map $F_λ(x)$, and a parameter-dependent matrix representation $M_λ$ defined over the univariate polynomial ring $\mathbb{F}[λ]$. Such a representation leads to the construction of a parametric inverse of such maps where the condition for invertibility is expressed through the unimodularity of this matrix representation $M_λ$. Apart from computing the compositional inverses of permutation polynomials, this linear representation is also used to compute the cycle structures of the permutation map. Lastly, this representation is extended to a representation of the cyclic group generated by a permutation map $F$, and to the group generated by a finite number of permutation maps over $\mathbb{F}$. |
| title | On Linear Representation, Complexity and Inversion of maps over finite fields |
| topic | Symbolic Computation Discrete Mathematics Representation Theory |
| url | https://arxiv.org/abs/2010.14601 |