Compositional inverses and complete mappings over finite fields (Q516831): Difference between revisions

Let \(\mathbb {F}_{q}\) be a finite field with \(q=p^m\) elements and \(f\in \mathbb {F}_{q}[x]\) a univariate polynomial. If \(f\) induces a permutation of \(\mathbb {F}_{q}\) under evaluation then there exists a unique \(f^{-1}\in \mathbb {F}_{q}[x]\) of degree less than \(q\) satisfying \(f(f^{-1}(x)) \equiv f^{-1}(f(x)) \equiv x \pmod{x^q-x}\). The paper under review studies this compositional inverse in case \(f\) is a linearized binomial permuting the kernel of the trace map \(T_{q^n|q^s}: \mathbb {F}_{q^n} \longrightarrow \mathbb {F}_{q^s}\), where \(s\) is a positive divisor of \(n\). In Theorem 2.4 it is shown that for any positive integer \(r\) such that \(d:=\gcd (n,r) =\gcd (r,s)\) and any \(c\in \mathbb {F}_{q^s}\) whose norm \(N^{q^s|q^d}(c)\) equals 1, the binomial \(L_{c,r}(x) :=x^{q^r}-cx\in \mathbb {F}_{q^n} [x]\) induces a permutation of \(\ker (T_{q^n|q^s})\) if and only if \(n/s\) is not divisible by the characteristic \(p\). Theorem 2.4 also contains an explicit formula for \(L_{c,r}^{-1}\) when it exists. This result is used in order to construct a class of complete mappings (i.e., permutation polynomials \(f\in \mathbb{F}_q [x]\) such that \(f(x)+x\) also permutes \(\mathbb {F}_{q}\)) for which the computational inverse is again explicitly obtained. A recursive construction of a set of complete mappings with the property that the difference of any two distinct elements permutes \(\mathbb {F}_{q}\) is also given.