Permutation Polynomial - Finite Fields

Finite Fields

There are many open questions concerning permutation polynomials defined over finite fields (see Lidl & Mullen (1988) and Lidl & Mullen (1993)).

If f(x) is a permutation polynomial defined over the finite field GF(q), where q = pe for some prime p, then so is g(x) = a f(x + b) + c for all a ≠ 0, b and c in GF(q). We say that g(x) is in normalized form if a, b and c are chosen so that g(x) is monic, g(0) = 0 and (provided the characteristic p does not divide the degree n of the polynomial) the coefficient of xn-1 is 0.

The following list, while not exhaustive, contains almost all of the known major classes of permutation polynomials over finite fields.

• Dickson (1958, pg. 63) lists all normalized permutation polynomials of degree at most 5.
• xk permutes GF(q) if and only if (k, q - 1) = 1.
• If a is in GF(q) then the Dickson polynomial g_k(x,a) permutes GF(q) if and only if (k, q2 - 1) = 1.
• If GF(qr) is an extension of GF(q) of degree r, then

with α_s in GF(qr) is a linear operator on GF(qr) over GF(q) and it permutes GF(qr) if and only if

• If r > 1 is relatively prime to q - 1, s divides q - 1 and g(xs) has no nonzero root in GF(q) where g(x) is in the polynomial ring GF(q), then xr(g(xs))(q - 1)/s permutes GF(q).
• Only a few other specific classes of permutation polynomials over GF(q) have been characterized. Two of these, for example, are:

where m divides q - 1, and

where d divides pn - 1.