A permutation polynomial (PP) over a finite field F_q is a polynomial over F_q that maps F_q onto itself, that is, permutes the elements of F_q. Permutation polynomials over finite fields, a subject of study for well over 100 years, have many applications in science and engineering. A polynomial f(x) over F_q is said to be a complete permutation polynomial (CPP) if both f(x) and f(x) + x are permutation polynomials. In this paper, the authors give four new classes of monomial CPPs, one new class of CPP trinomials, and two new classes of trinomial PPs. For example, one of the classes of monomial CPPs is defined as follows: Let p = r + 1 be an odd prime and d = p^rk - 1/p^k-1 + 1. Then a^-1x^d is a CPP over F_p^rk where a ∈ F_p^rk is such that a^pk-1 = -1. This proves a conjecture of Gaofel Wu et al. [1].

Monomial permutations are relatively cheap to implement in hardware and for this reason they are suitable candidates for S-boxes in block ciphers. S-boxes must have low “differential uniformity” in order for the cipher to resist attacks. C. Blondeau et al. [2] conjectured that for certain values of d, the differential uniformity δ(F_d) of x^d over F_2^2m is 8. In the last section, the authors prove that this is at most 10.