MAGMA Computational Algebra System

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) = ∑_i=0^{⌊n/2 ⌋} (n /(n - i)) ((n - i) choose i) ( - a)ⁱ 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) = ∑_i=0^{⌊n/2 ⌋} ((n - i) choose (i)) ( - a)ⁱ 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 FldFin_Dickson (H21E6)

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

> 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₃ (x, a) is not a permutation polynomial. However, D₄ (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