[quibble^2] Quoting Warren D Smith <warren.wds@gmail.com>: [moby clippage -- rich]
RCS: For the other group generator, either A(x) = x+1, or G(x) = gx with g a primitive root may be used. WDS: [clip, not relevant to my quibble^2] RCS: For higher degree extensions GF[p^e], A is no longer a single loop, but G is still a single loop, WDS: [clip] 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.
Minor quibble: The map f(x)->2x (mod 5) is a loop (+ a singleton fixed point x=0), but in GF[25] it's several loops. Multipliers from the ground field GF[5] aren't primitive roots in GF[25]. Many of the other elements in GF[25] are primitive roots.
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."
This is true. My calling G a single loop is inaccurate in neglecting the fixed point. However, the two generators S=(01) and G=(1,g,...) DO generate the full permutation group (when loop G includes everything except 0): The permutation SG is a full length loop, inserting 0 into the G loop between 1 and g: SG = (1,0,g,g2,...,1/g).
WDS: it was anyhow obvious that the polynomials of degree<q generate all maps if GF(q) to self, by use of Lagrange interpolation.
"obvious" is in the eye of the beholder.
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?
I'd like to see this too. It seems unlikely for non-linear polynomials: (all mod P): We require F(x)/=F(y) unless x=y. But F(x+1)-F(x) will be another polynomial G of lower degree. If we choose a random n, and let P be any prime dividing G(n) = F(n+1)-F(n), then F(x) mod P isn't a permutation, because F(n)=F(n+1) mod P. The patched-reciprocal R(x) = {1/x, except R(0)=0} is a permutation, so probably all the (ax+b)/(cx+d) are too, with a similar patch, and excluding p|ad-bc. Rich