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#

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}\).

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

Run in calculator

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

> 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

Run in calculator

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

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

Run in calculator