# Permutation Polynomials

Let $K$ be a finite field. A polynomial representing (by the evaluation map) a bijection of $K$ into itself is known as a *permutation polynomial*. The Dickson polynomials of the first and second kind are permutation polynomials when certain conditions are satisfied.

## `DicksonFirst(n, a): RngIntElt, RngElt -> RngUPolElt`

Given a positive integer $n$, this function constructs the Dickson polynomial of the first kind $D_n (x, a)$ of degree $n$, where $D_n (x, a)$ is defined by

$$
D_n(x, a) = \sum_{i=0}^{\lfloor n/2 \rfloor}
   {n \over {n - i}} {{n - i} \choose i} (-a)^i x^{n - 2i}.
$$

## `DicksonSecond(n, a): RngIntElt, RngElt -> RngUPolElt`

Given a positive integer $n$, this function constructs the Dickson polynomial of the second kind $E_n (x, a)$ of degree $n$, where $E_n (x, a)$ is defined by

$$
E_n(x, a) = \sum_{i=0}^{\lfloor n/2 \rfloor}
   {{n - i} \choose {i}} (-a)^i x^{n - 2i}.
$$

## `IsProbablyPermutationPolynomial(p): RngUPolElt -> BoolElt`

```magma
NumAttempts: RngIntElt                    Default: 100
```

Let $p$ denote a polynomial defined over a finite field $K$. A probabilistic test is applied to determine whether the mapping on $K$ defined by $p$ is a bijection. The function returns `true` if the test succeeds for each of $n$ attempts, otherwise `false`. By default, $n$ is taken to be 100; a different value for $n$ can be specified by use of the parameter `NumAttempts`.

## `Example: Dickson (ex-41c38e)`

Let $K$ be a finite field of cardinality $q$. By a theorem of Nöbauer, the Dickson polynomial of the first kind of degree $n$ is a permutation polynomial for $K$ if and only if $(n, q^2 -1)=1$. Consider $K={\bf F}_{16}$.

```magma
> Factorization(16^2 - 1);
[ <3, 1>, <5, 1>, <17, 1> ]

```

Thus, $D_n (x, a)$ will be a permutation polynomial for $K$ providing that $n$ is coprime to 3, 5 and 17.

```magma
> K<w> := GF(16);
> R<x> := PolynomialRing(K);
> a := w^5;
> p1 := DicksonFirst(3, a);
> p1;
x^3 + w^5*x
> #{ Evaluate(p1, x) : x in K };
11
> IsProbablyPermutationPolynomial(p1);
false

```

So $D_3 (x, a)$ is not a permutation polynomial. However, $D_4 (x, a)$ is a permutation polynomial:

```magma
> p1 := DicksonFirst(4, a);
> p1;
x^7 + w^5*x^5 + x
> #{ Evaluate(p1, x) : x in K };
16
> IsProbablyPermutationPolynomial(p1);
true

```