Permutation polynomial

Hermite's criterion is computationally intensive and can be difficult to use in making theoretical conclusions. However, Dickson was able to use it to find all permutation polynomials of degree at most five over all finite fields. These results are:[9][6]

Normalized Permutation Polynomial of Fq	q
${\displaystyle x}$	any ${\displaystyle q}$
${\displaystyle x^{2}}$	${\displaystyle q\equiv 0\!{\pmod {2}}}$
${\displaystyle x^{3}}$	${\displaystyle q\not \equiv 1\!{\pmod {3}}}$
${\displaystyle x^{3}-ax}$ (${\displaystyle a}$ not a square)	${\displaystyle q\equiv 0\!{\pmod {3}}}$
${\displaystyle x^{4}\pm 3x}$	${\displaystyle q=7}$
${\displaystyle x^{4}+a_{1}x^{2}+a_{2}x}$ (if its only root in Fq is 0)	${\displaystyle q\equiv 0\!{\pmod {2}}}$
${\displaystyle x^{5}}$	${\displaystyle q\not \equiv 1\!{\pmod {5}}}$
${\displaystyle x^{5}-ax}$ (${\displaystyle a}$ not a fourth power)	${\displaystyle q\equiv 0\!{\pmod {5}}}$
${\displaystyle x^{5}+ax\,(a^{2}=2)}$	${\displaystyle q=9}$
${\displaystyle x^{5}\pm 2x^{2}}$	${\displaystyle q=7}$
${\displaystyle x^{5}+ax^{3}\pm x^{2}+3a^{2}x}$ (${\displaystyle a}$ not a square)	${\displaystyle q=7}$
${\displaystyle x^{5}+ax^{3}+5^{-1}a^{2}x}$ (${\displaystyle a}$ arbitrary)	${\displaystyle q\equiv \pm 2\!{\pmod {5}}}$
${\displaystyle x^{5}+ax^{3}+3a^{2}x}$ (${\displaystyle a}$ not a square)	${\displaystyle q=13}$
${\displaystyle x^{5}-2ax^{3}+a^{2}x}$ (${\displaystyle a}$ not a square)	${\displaystyle q\equiv 0\!{\pmod {5}}}$

A list of all monic permutation polynomials of degree six in normalized form can be found in Shallue & Wanless (2013).[10]

Beyond the above examples, the following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.[11]

• xⁿ permutes GF(q) if and only if n and q − 1 are coprime (notationally, (n, q − 1) = 1).[12]
• If a is in GF(q) and n ≥ 1 then the Dickson polynomial (of the first kind) D_n(x,a) is defined by
  $${\displaystyle D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {n-j}{j}}(-a)^{j}x^{n-2j}.}$$

  

These can also be obtained from the recursion

$${\displaystyle D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),}$$

with the initial conditions ${\displaystyle D_{0}(x,a)=2}$ and ${\displaystyle D_{1}(x,a)=x}$. The first few Dickson polynomials are:

• ${\displaystyle D_{2}(x,a)=x^{2}-2a}$
• ${\displaystyle D_{3}(x,a)=x^{3}-3ax}$
• ${\displaystyle D_{4}(x,a)=x^{4}-4ax^{2}+2a^{2}}$
• ${\displaystyle D_{5}(x,a)=x^{5}-5ax^{3}+5a^{2}x.}$

If a ≠ 0 and n > 1 then D_n(x, a) permutes GF(q) if and only if (n, q² − 1) = 1.[13] If a = 0 then D_n(x, 0) = xⁿ and the previous result holds.

• If GF(q^r) is an extension of GF(q) of degree r, then the linearized polynomial
  $${\displaystyle L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},}$$

  
  with α_s in GF(q^r), is a linear operator on GF(q^r) over GF(q). A linearized polynomial L(x) permutes GF(q^r) if and only if 0 is the only root of L(x) in GF(q^r).[12] This condition can be expressed algebraically as[14]
  $${\displaystyle \det \left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).}$$

  

The linearized polynomials that are permutation polynomials over GF(q^r) form a group under the operation of composition modulo ${\displaystyle x^{q^{r}}-x}$, which is known as the Betti-Mathieu group, isomorphic to the general linear group GL(r, F_q).[14]

• If g(x) is in the polynomial ring F_q[x] and g(x^s) has no nonzero root in GF(q) when s divides q − 1, and r > 1 is relatively prime (coprime) to q − 1, then x^r(g(x^s))^{(q - 1)/s} permutes GF(q).[6]
• Only a few other specific classes of permutation polynomials over GF(q) have been characterized. Two of these, for example, are:
  $${\displaystyle x^{(q+m-1)/m}+ax}$$

  
  where m divides q − 1, and
  $${\displaystyle x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}}$$

  
  where d divides pⁿ − 1.

An exceptional polynomial over GF(q) is a polynomial in F_q[x] which is a permutation polynomial on GF(q^m) for infinitely many m.[15]

A permutation polynomial over GF(q) of degree at most q^1/4 is exceptional over GF(q).[16]

Every permutation of GF(q) is induced by an exceptional polynomial.[16]

If a polynomial with integer coefficients (i.e., in ℤ[x]) is a permutation polynomial over GF(p) for infinitely many primes p, then it is the composition of linear and Dickson polynomials.[17] (See Schur's conjecture below).

Consider ${\displaystyle g(x)=2x^{2}+x}$ for the ring Z/4Z. One sees: ${\displaystyle g(0)=0}$; ${\displaystyle g(1)=3}$; ${\displaystyle g(2)=2}$; ${\displaystyle g(3)=1}$, so the polynomial defines the permutation

$${\displaystyle {\begin{pmatrix}0&1&2&3\\0&3&2&1\end{pmatrix}}.}$$

Consider the same polynomial ${\displaystyle g(x)=2x^{2}+x}$ for the other ring Z/8Z. One sees: ${\displaystyle g(0)=0}$; ${\displaystyle g(1)=3}$; ${\displaystyle g(2)=2}$; ${\displaystyle g(3)=5}$; ${\displaystyle g(4)=4}$; ${\displaystyle g(5)=7}$; ${\displaystyle g(6)=6}$; ${\displaystyle g(7)=1}$, so the polynomial defines the permutation

$${\displaystyle {\begin{pmatrix}0&1&2&3&4&5&6&7\\0&3&2&5&4&7&6&1\end{pmatrix}}.}$$

Consider ${\displaystyle g(x)=ax^{2}+bx+c}$ for the ring Z/p^kZ.

Lemma: for k=1 (i.e. Z/pZ) such polynomial defines a permutation only in the case a=0 and b not equal to zero. So the polynomial is not quadratic, but linear.

Lemma: for k>1, p>2 (Z/p^kZ) such polynomial defines a permutation if and only if ${\displaystyle a\equiv 0{\pmod {p}}}$ and ${\displaystyle b\not \equiv 0{\pmod {p}}}$.

Consider ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$, where p_t are prime numbers.

Lemma: any polynomial ${\textstyle g(x)=a_{0}+\sum _{0<i\leq M}a_{i}x^{i}}$ defines a permutation for the ring Z/nZ if and only if all the polynomials ${\textstyle g_{p_{t}}(x)=a_{0,p_{t}}+\sum _{0<i\leq M}a_{i,p_{t}}x^{i}}$ defines the permutations for all rings ${\displaystyle Z/p_{t}^{k_{t}}Z}$, where ${\displaystyle a_{j,p_{t}}}$ are remainders of ${\displaystyle a_{j}}$ modulo ${\displaystyle p_{t}^{k_{t}}}$.

As a corollary one can construct plenty quadratic permutation polynomials using the following simple construction. Consider ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{l}^{k_{l}}}$, assume that k₁ >1.

Consider ${\displaystyle ax^{2}+bx}$, such that ${\displaystyle a=0{\bmod {p}}_{1}}$, but ${\displaystyle a\neq 0{\bmod {p}}_{1}^{k_{1}}}$; assume that ${\displaystyle a=0{\bmod {p}}_{i}^{k_{i}}}$, i > 1. And assume that ${\displaystyle b\neq 0{\bmod {p}}_{i}}$ for all i = 1, ..., l. (For example, one can take ${\displaystyle a=p_{1}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$ and ${\displaystyle b=1}$). Then such polynomial defines a permutation.

To see this we observe that for all primes p_i, i > 1, the reduction of this quadratic polynomial modulo p_i is actually linear polynomial and hence is permutation by trivial reason. For the first prime number we should use the lemma discussed previously to see that it defines the permutation.

For example, consider Z/12Z and polynomial ${\displaystyle 6x^{2}+x}$. It defines a permutation ${\begin{pmatrix}0&1&2&3&4&5&6&7&8&\cdots \\0&7&2&9&4&11&6&1&8&\cdots \end{pmatrix}}.$