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

Read more about this topic:  Permutation Polynomial

Famous quotes containing the words finite and/or fields:

    We know then the existence and nature of the finite, because we also are finite and have extension. We know the existence of the infinite and are ignorant of its nature, because it has extension like us, but not limits like us. But we know neither the existence nor the nature of God, because he has neither extension nor limits.
    Blaise Pascal (1623–1662)

    ... my one aim and concentrated purpose shall be and is to show that women can learn, can reason, can compete with men in the grand fields of literature and science ... that a woman can be a woman and a true one without having all her time engrossed by dress and society.
    M. Carey Thomas (1857–1935)