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.
Given a positive integer n, this function constructs the Dickson polynomial of the first kind Dn (x, a) of degree n, where Dn (x, a) is defined by Dn(x, a) = ∑i=0⌊n/2 ⌋ (n /(n - i)) ((n - i) choose i) ( - a)i xn - 2i.
Given a positive integer n, this function constructs the Dickson polynomial of the second kind En (x, a) of degree n, where En (x, a) is defined by En(x, a) = ∑i=0⌊n/2 ⌋ ((n - i) choose (i)) ( - a)i xn - 2i.
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.
> Factorization(16^2 - 1); [ <3, 1>, <5, 1>, <17, 1> ]
Thus, Dn (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
So D3 (x, a) is not a permutation polynomial. However, D4 (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