The function S(x) = (x-1)^(p-1) - x^(p-1) + x in GF(p) swaps 0 and 1, and fixes the other residues. 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. For higher degree extensions GF[p^e], A is no longer a single loop, but G is still a single loop, though g must be from the extension field. The exponents in S become p^e-1, and the mod polynomial become 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]. Rich ------ Quoting Henry Baker <hbaker1@pipeline.com>:
So Dickson worked on this problem in 1896 ! I'll have to track down his work.
Thanks very much, Victor -- I thought there might be some literature on this problem, but I didn't know what to search for. I guessed correctly that other people also called them "permutation polynomials".
At 06:46 PM 3/19/2016, Victor Miller wrote:
My former colleague, Mike Zieve (now a professor at MIchigan) has written a number of papers about permutation polynomials, the latest is http://arxiv.org/pdf/1312.1325.pdf . It gives a lot of references to known results and to his previous work.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun