---
title: "Permutation Polynomials"
canonical: "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/permutation-polynomials.html"
source: "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/permutation-polynomials.md"
part: "Basic Rings"
chapter: "Finite Fields"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Basic Rings", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/index-basic-rings.md"}
  - {"title": "Finite Fields", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/index-finite-fields.md"}
prev: {"title": "Discrete Logarithms", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/log.md"}
next: {"title": "Bibliography", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/FiniteFields/bibliography.md"}
intrinsics:
  - {"name": "DicksonFirst", "signature": "DicksonFirst(n, a): RngIntElt, RngElt -> RngUPolElt"}
  - {"name": "DicksonSecond", "signature": "DicksonSecond(n, a): RngIntElt, RngElt -> RngUPolElt"}
  - {"name": "IsProbablyPermutationPolynomial", "signature": "IsProbablyPermutationPolynomial(p): RngUPolElt -> BoolElt"}
examples:
  - "ex-41c38e"
---

# 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.

<a id="function-dicksonfirst-rngintelt-rngelt"></a>
## `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}.
$$

<a id="function-dicksonsecond-rngintelt-rngelt"></a>
## `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}.
$$

<a id="function-isprobablypermutationpolynomial-rngupolelt"></a>
## `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`.

<a id="example-ex-41c38e"></a>
## `Example: Dickson Permutation Polynomials (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
```
