Let's assume you have a polynomial over a finite field $\F_q$, defined in Sage. How can you tell whether it's a permutation polynomial? That is, when is the corresponding function $\F_q\to\F_q$ bijective?

This is how you might have a polynomial over $\F_q$ defined in Sage:

1 2 3 |
R.<x> = GF(q) S.<t> = PolynomialRing(R) f = 1 + x*t^2 |

Here, the variable $x$ refers the element $x$ in the isomorphism $\F_q \cong \F_p[x]/\alpha(x)$ and $t$ is the variable in the polynomial ring $\F_q[t]$. Is $f$ a permutation polynomial? That of course depends on what $q$ is.

More »