论文标题
在有限场上的线性表示，复杂性和地图的反转
On Linear Representation, Complexity and Inversion of maps over finite fields
论文作者
论文摘要
本文定义了非线性映射$ f的线性表示形式：\ mathbb {f}^n \ rightArrow \ mathbb {f}^n $其中$ \ mathbb {f} $是一个有限字段，就$ \ m m i \ m m 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$.结果表明，对于带有表示$ m $的置换映射$ f $，逆映射具有线性表示$ m^{ - 1} $。该表示的框架扩展到了一个映射$f_λ（x）的参数化家族：\ Mathbb {f} \至\ Mathbb {f} $，根据参数$λ\ in \ Mathbb {f} $定义，导致了$ F_ $ f _ MAT $ f_λ的类似线性复杂性的定义$m_λ$在单变量多项式环$ \ mathbb {f} [λ] $上定义。这种表示形式导致构建此类地图的参数倒数，在这种地图中，可逆性条件通过此矩阵表示$m_λ$的单对形表示。除了计算置换多项式的组成逆外，该线性表示还用于计算置换图的循环结构。最后，该表示形式扩展到由置换映射$ f $生成的循环组的表示，以及由有限数量的置换图生成的组上的$ \ mathbb {f} $生成的组。
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}$.
