Scratch that reasoning! x^3 is a perm poly mod 5, & has a repeated root! At 12:51 PM 3/29/2016, Henry Baker wrote:
Permutation polynomials aren't so easy to factor -- at least not into 2 factors that are both permutations.
Suppose that a permutation poly p(x) factors into q(x)*r(x), where q(x) & r(x) are also perm polys. But p(x) must have exactly 1 root, else two distinct roots map into zero. But since q(x) and r(x) are also perm polys, they must each have a single root. If they are different, then p(x) would have two distinct roots, a contradiction. If q(x) and r(x) share the same root, then p(x) has a repeated root. But if p(x) has a repeated root, then by the pigeonhole principle, there is some field element without a preimage via p(x), so p(x) can't be a permutation poly -- once again a contradiction. So a permutation poly can't possibly factor into two permutation polys.
The same argument works for any number of factors on the right hand side, so a permutation polynomial can't factor into multiple permutation polynomials, either.
By the above reasoning, if p(x)=q(x)*r(x), and p(x), q(x) are permutation polynomials, then p(x) & q(x) must share the same zero, and r(x) has *no* zeros -- i.e., r(x) has no linear factors.