A general construction of permutation polynomials of F_q^2

Polynomials over finite fields (11T06) Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Arithmetic theory of polynomial rings over finite fields (11T55)

Abstract: Let

r

be a positive integer,

h (X) i n B b b F_{q^{2}} [X]

, and

m u_{q + 1}

be the subgroup of order

q + 1

of

B b b F_{q^{2}}^{*}

. It is well known that

X^{r} h (X^{q - 1})

permutes

B b b F_{q^{2}}

if and only if

e x t g c d (r, q - 1) = 1

and

X^{r} h (X)^{q - 1}

permutes

m u_{q + 1}

. There are many ad hoc constructions of permutation polynomials of

B b b F_{q^{2}}

of this type such that

h (X)^{q - 1}

induces monomial functions on the cosets of a subgroup of

m u_{q + 1}

. We give a general construction that can generate, through an algorithm, {em all} permutation polynomials of

B b b F_{q^{2}}

with this property, including many which are not known previously. The construction is illustrated explicitly for permutation binomials and trinomials.

Review text

Let \(p\) be a prime, \(q\) a power of \(p\), and \(\mathbb{F}_q\) denote the finite field with \(q\) elements. A polynomial \(f\in \mathbb{F}_q[x]\) is called a \textit{permutation polynomial} (PP) of \(\mathbb{F}_q\) if the associated mapping \(x\mapsto f(x)\) from \(\mathbb{F}_q\) to \(\mathbb{F}_q\) is a permutation of \(\mathbb{F}_q\). Let \(r\) be a positive integer, \(d\,|\,q-1\), and \(h(X)\in \mathbb{F}_q[x]\). It is well known that \(X^rh(X^{(q-1)/d})\) is a permutation polynomial of \(\mathbb{F}_q\) if and only if \(\text{gcd}(r,(q-1)/d)=1\) and \(X^rh(X)^{(q-1)/d}\) permutes the multiplicative group \(\mu_d:=\{x\in \mathbb{F}_q^*\,:\,x^d=1\}\). Replacing \(q\) with \(q^2\) and \(d\) with \(q+1\), we see that for \(h(X)\in \mathbb{F}_{q^2}[X]\), \(X^rh(X^{q-1})\) is a permutation polynomial of \(\mathbb{F}_{q^2}\) if and only if \(\text{gcd}(r,q-1)=1\) and \(X^rh(X)^{q-1}\) permutes \(\mu_{q+1}\). The following idea has been used by several authors to construct permutations of \(\mu_{q+1}\) of the form \(X^rh(X)^{q-1}\): Let \(H\) be a subgroup of \(\mu_{q+1}\) of small index. Construct a polynomial \(h(X)\in\mathbb{F}_{q^2}[X]\) such that \(h(X)^{q-1}\) induces monomial functions on each coset of \(H\) in \(\mu_{q+1}\). With such a property, \(X^rh(X)^{q-1}\) permutes \(\mu_{q+1}\) if and only if some simple number theoretic conditions on the parameters are satisfied. This method has produced many results. However, these results only deal with specific situations, leaving a unified treatment to be desired. In the paper under review, the authors take a general approach to the question. The main result is an algorithm, which is given at the end of this review, that produces {\em all} permutation polynomials of \(\mathbb{F}_{q^2}\) of the form \(X^rh(X^{q-1})\) such that \(h(X)^{q-1}\) induces monomial functions on the cosets of a subgroup in \(\mu_{q+1}\). The authors determine all permutation polynomials of \(\mathbb{F}_{q^2}\) resulting from this algorithm and it turns out that all these permutation binomials were all known previously. The authors also determine all permutation trinomials of \(\mathbb{F}_{q^2}\) resulting from the algorithm. There are four classes of such permutation trinomials, excluding those that were previously known. These four classes, in their generality, appear to be new, although many special cases have been discovered by other authors. Overall, this approach reveals many permutation polynomials that were not known previously. \textbf{Algorithm} Let \(r\) be a positive integer such that \(gcd(r,q-1)=1\) and let \(d\mid q+1\). \medskip \textbf{Input:} Sequences \(s_k\), \(t_k\), \(\tau_k\), \(\pi(k)\), \(\lambda_k\), \(0\le k<d\), described below. \medskip \textbf{Output:} A PP of \(\mathbb{F}_{q^2}\) of the form \(X^rh(X^{q-1})\) such that \(X^rh(X)^{q-1}\) is a monomial function on each \(A_k\), \(0\le k<d\). \medskip \textbf{Note:} All PPs of \(\mathbb{F}_{q^2}\) with such properties can be produced by this algorithm. \textbf{Step 1} Choose integer sequence \(s_k,t_k,\tau_k\ge \), \(0\le k<d\), such that \(s_k+t_k<(q+1)/d\), \(\tau_k\in\{0\}\cup[(q+1)/d-t_k,t_k]\), and \(e_k:=r-2s_k-t_k+\tau_k\) satisfies \(\gcd(e_k,(q+1)/d)=1\). \textbf{Step 2} Choose a sequence \(\pi(k)\in\mathbb Z/d\mathbb Z\), \(0\le k<d\), such that \(k\mapsto \pi(k)+e_kk\) permutes \(\mathbb Z/d\mathbb Z\). \textbf{Step 3} For each \(0\le k<d\), choose \(\lambda_k\in A_{\pi(k)}\) and \(L_k\in\mathcal L_k(t_k,\tau_k;\lambda_k)\). \medskip \textbf{Step 4} Compute the \(((q+1)/d)\times d\) matrix \([M_{ik}]\) such that \[ X^{s_k}L_k=\sum_iM_{ik}X^i, \] and compute the \(((q+1)/d)\times d\) matrix \[ [a_{ij}]=\frac 1d[M_{ik}][\varepsilon^{-kj}]. \] \textbf{Step 5} Let \[ h(X)=\sum_{i,j}a_{ij}X^{i+j(q+1)/d}. \] Then \(X^rh(X^{q-1})\) is the output PP of \(\mathbb{F}_{q^2}\). \textbf{Remark} In Step 3, when choosing \(L_k\in\mathcal L_k(t_k,\tau_k;\lambda_k)\), it is required that \(\gcd(L_k,X^{(q+1)/d}-\varepsilon^k)=1\). However, this condition is automatically satisfied if \(h(X)\) in Step 5 satisfies \(\gcd(h,X^{q+1}-1)=1\). In fact, \(\gcd(L_k,X^{(q+1)/d}-\varepsilon^k)=1\) for all \(0\le k<d\) if and only if \(\gcd(h,X^{q+1}-1)=1\).

Recommendations

Cites work

Cited in

(14)

This page was built for publication: A general construction of permutation polynomials of \(\mathbb{F}_{q^2}\)

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