RCS: The function S(x) = (x-1)^(p-1) - x^(p-1) + x in GF(p) swaps 0 and 1, and fixes the other residues. WDS: Verify directly for 0 and 1; use Lagrange theorem that x^(p-1)=1 if x>0 for all other x mod p. Check. RCS: For the other group generator, either A(x) = x+1, or G(x) = gx with g a primitive root may be used. Composing these in all possible ways, while reducing mod x^p-x, generates the permutations. WDS: correct: x+1 is the p-cycle, and the 01 swap is then all you need to generate every permutation. The reduction modulo x^p-x causes the reduced polynomial to have degree<p. RCS: For higher degree extensions GF[p^e], A is no longer a single loop, but G is still a single loop, WDS: this cyclic-multiplicative-group fact is a theorem by E.Galois. Proofs are available in 1 Andre Weil: Basic number theory, on page 2, can read this page online here http://www.amazon.com/Basic-Number-Theory-Classics-Mathematics/dp/3540586555 2 J-P. Serre: A course in arithmetic, 3 Loo-Keng Hua: Introduction to number theory However: A. I disagree with RCS: though g must be from the extension field. Actually, g is a plain old field element, and Weil proves that. B. And the loop is among the q-1 NONZERO elements of GF(q), where q=p^e, not ALL elements like for x+1 if q prime. So it really is "a single loop plus an isolani." However, using S(x-K) rather than S(x) swaps K and K+1. Therefore, we can by composing S(x-K) and g*x in all possible ways reducing modulo x^p-x as RCS says, generate all permutations of the nonzero elements of GF(q). We then can also swap 0 with 1 using S(x)... which enables seeing that all permutations of the whole kaboodle, are accessible. RCS: The exponents in S become p^e-1, and the mod polynomial becomes x^p^e - x. Returning to GF[p]: If you add a third generator, L(x) = x + 1 - x^(p-1), which maps 0->1 and everything else to self, thereby losing some information, you can generate all the maps from GF[p]->GF[p]. These are 1-1 with the polynomials of degree < p. Similarly for GF[p^e]. WDS: it was anyhow obvious that the polynomials of degree<q generate all maps if GF(q) to self, by use of Lagrange interpolation. It seems to me this whole short post by RCS, is brilliantly simple, and (after my slight corrections) totally characterizes and constructs all permutation polynomials over all finite fields. However, there still is this criticism: what if I want the perm polynomials which work REGARDLESS of the value of q? RCS's generation method sort of handles each GF(q) by itself, it does not handle all of them in a unified way. So for example, the fact that x^k is a permutation polynomial in GF(q) if GCD(k,q-1)=1, which is fairly obvious from Galois' theorem, is not so obvious from RCS's construction (is it?). Is there a way to overcome this criticism? And by the way, to mention the obvious, see https://en.wikipedia.org/wiki/Permutation_polynomial which also gives the following beautiful characterization of the perm polynomials over the ring Z mod p^e: F(x) is a perm polynomial if and only if 1. it permutes Z mod p, and 2. F'(x) is nonzero for every ring element x. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)