Dickson polynomials that are involutions (Q2829797)

The Dickson polynomial \(D_k(x)\in\mathbb Z[x]\) is defined by the functional equation NEWLINE\[NEWLINED_k(x+x^{-1})=x^k+x^{-k},NEWLINE\]NEWLINE where \(k\geq 0\) is an integer. In the paper under review, \(D_k(x)\) is treated as a polynomial in \(\mathbb F_2[x]\). It is well known that \(D_k(x)\) is a permutation polynomial of \(\mathbb F_{2^m}\) if and only if \(\text{gcd}(k,2^{2m}-1)=1\). The paper deals with the Dickson polynomials \(D_k(x)\) that are involutions of \(\mathbb F_{2^m}\), i.e., those \(D_k(x)\) such that \(D_k\circ D_k\) is the identity map of \(\mathbb F_{2^m}\). The motivation is that in cryptography, such a polynomial serves for both encryption and decryption.NEWLINENEWLINELet \(\mathfrak S_{\mathbb F_{2^m}}\) be the group of all permutations of \(\mathbb F_{2^m}\). Then the map \(\mathbb Z_{2^{2m}-1}^\times\to \mathfrak S_{\mathbb F_{2^m}}\), \(k\mapsto D_k(x)\), is a well-defined group homomorphism with kernel \(K_{2m}=\{\pm 1,\pm 2^m\}\); this homomorphism induces an embedding \(\mathbb Z_{2^{2m}-1}^\times/K_{2m}\to \mathfrak S_{\mathbb F_{2^m}}\). Let \(S_{2m}=\{u\in\mathbb Z_{2^{2m}-1}^\times:u^2=1\}\) be the subgroup of \(\mathbb Z_{2^{2m}-1}^\times\) consisting of elements of order \(1\) and \(2\). Then the subgroup of \(\mathbb Z_{2^{2m}-1}^\times/K_{2m}\) consisting of elements of order \(1\) and \(2\) is NEWLINE\[NEWLINE\begin{cases} S_{2m}/K_{2m}&\text{if \(m\) is odd},\\ (S_{2m}\cup 2^{m/2}S_{2m})/K_{2m}&\text{if \(m\) is even}. \end{cases}\tag{\(*\)}NEWLINE\]NEWLINE The structure of the groups in (\(*\)) can be made explicit once the factorization of \(2^{2m}-1\) is known.NEWLINENEWLINEThe indices \(k\in\mathbb Z_{2^{2m}-1}^\times/K_{2m}\) for which \(D_k(x)\) is an involution of \(\mathbb F_{2^m}\) are precisely the elements of the groups in (\(*\)). The paper first establishes the facts in the above paragraph (in equivalent forms) with detailed proofs. A number of further topics are discussed in the rest of the paper. The number of nontrivial Dickson involutions of \(\mathbb F_{2^m}\) is determined. Two explicit classes of indices \(k\) giving rise to Dickson involutions \(D_k(x)\) of \(\mathbb F_{2^m}\) are constructed. Using an existing formula for the number of fixed points of a Dickson permutation polynomial, the authors investigate the minimum number of fixed points of all Dickson involutions of \(\mathbb F_{2^m}\). When \(m\) is even, the minimum number is \(2^{m/2}\); when \(m\) is odd, two lower bounds for the minimum number are given. Moreover, for even \(m\), all Dickson involutions \(D_k(x)\) of \(\mathbb F_{2^m}\) with precisely \(2^{m/2}\) fixed points are determined; in this case, the set of fixed points of \(D_k(x)\) is \(\mathbb F_{2^{m/2}}\). The paper contains several examples and some numerical results.NEWLINENEWLINEFor the entire collection see [Zbl 1345.11003].